Главная
Спектр графа (англ. graph spectrum) - это множество собственных значений матрицы смежности графа.
Спектр может быть определен как для простого графа, так и для орграфа, мультиграфа, псевдографа или псевдомультиграфа.
Определения
Пусть Γ ( V , E ) {displaystyle Gamma (V,E)} - граф, где V ( Γ ) {displaystyle V(Gamma )} есть множество его вершин v ∈ V ( Γ ) {displaystyle vin V(Gamma )} , а E ( Γ ) {displaystyle E(Gamma )} есть множество его ребер e ∈ E ( Γ ) {displaystyle ein E(Gamma )} . Кардинальное число n = | V ( Γ ) | {displaystyle n=|V(Gamma )|} есть количество вершин графа.
Смежными вершинами графа Γ {displaystyle Gamma } являются вершины v 1 {displaystyle v_{1}} и v 2 {displaystyle v_{2}} такие, что { v 1 , v 2 } ∈ E ( G ) {displaystyle left{v_{1},v_{2} ight}in E(G)} или, другими словами, обе вершины являются концевыми для одного ребра.
Матрица смежности для простого графа Γ {displaystyle Gamma } есть матрица A {displaystyle mathbf {A} } размера n × n {displaystyle n imes n} где:
a i , j = { 1 : { v i , v j } ∈ E ( G ) , 0 : { v i , v j } ∉ E ( G ) {displaystyle a_{i,j}={egin{cases}1&:,left{v_{i},v_{j} ight}in E(G), &:,left{v_{i},v_{j} ight} otin E(G)end{cases}}} ,то есть элемент матрицы a i , j {displaystyle a_{i,j}} равен единице, если вершины v i {displaystyle v_{i}} и v j {displaystyle v_{j}} смежны, и равен нулю, если нет, причем a i , i = 0 {displaystyle a_{i,i}=0} .
Для псевдографа элемент a i , i {displaystyle a_{i,i}} равен удвоенному числу петель, присоединенных к вершине v i {displaystyle v_{i}} . Также возможен однократный учет петель. Ориентированная петля учитывается однократно.
Для мультиграфа элемент a i , j {displaystyle a_{i,j}} равен числу кратных ребер e = { v i , v j } {displaystyle e=left{v_{i},v_{j} ight}} .
Характеристический многочлен графа P G ( λ ) {displaystyle P_{G}(lambda )} есть характеристический многочлен его матрицы смежности d e t ( λ I − A ) = 0 {displaystyle det(lambda mathbf {I} -mathbf {A} )=0} :
P G ( λ ) = λ n + c 1 λ n − 1 + c 2 λ n − 2 + c 3 λ n − 3 + ⋯ + c n {displaystyle P_{G}(lambda )=lambda ^{n}+c_{1}lambda ^{n-1}+c_{2}lambda ^{n-2}+c_{3}lambda ^{n-3}+dots +c_{n}}Собственный вектор графа x {displaystyle mathbf {x} } есть собственный вектор матрицы смежности :
A x = λ x {displaystyle mathbf {A} mathbf {x} =lambda mathbf {x} }Определения спектра графа
В работе спектр графа определен как множество собственных чисел λ i {displaystyle lambda _{i}} характеристического многочлена графа (или собственных чисел графа), где λ 0 ⩽ λ 1 ⩽ ⋯ ⩽ λ s {displaystyle lambda _{0}leqslant lambda _{1}leqslant dots leqslant lambda _{s}} и кратностей этих чисел m ( λ i ) {displaystyle m(lambda _{i})}
S p e c ( Γ ) = ( λ 0 λ 1 … λ s − 1 m ( λ 0 ) m ( λ 1 ) … m ( λ s − 1 ) ) {displaystyle Spec(Gamma )={egin{pmatrix}lambda _{0}&lambda _{1}&dots &lambda _{s-1}m(lambda _{0})&m(lambda _{1})&dots &m(lambda _{s-1})end{pmatrix}}}В работе спектр графа определен просто как множество собственных чисел:
S p ( Γ ) = [ λ 1 , λ 2 , … , λ n ] {displaystyle Sp(Gamma )=left[lambda _{1},,lambda _{2},,dots ,,lambda _{n} ight]}Свойства
Коэффициенты c i {displaystyle c_{i}} характеристического многочлена графа Γ {displaystyle Gamma } удовлетворяют условиям:
- c 1 = 0 {displaystyle c_{1}=0}
- − c 2 {displaystyle -c_{2}} - есть число ребер графа Γ {displaystyle Gamma }
- − c 3 {displaystyle -c_{3}} - есть удвоенное число треугольников графа Γ {displaystyle Gamma }