Spectrul graficului

Un spectru grafic este un set de valori proprii ale matricei de adiacență a unui grafic.

Spectrul poate fi definit atât pentru un grafic simplu, cât și pentru un digraf , multigraf , pseudograf sau pseudomultigraf .

Definiții

Fie un grafic în care există o mulțime de vârfuri și există o mulțime de muchii . Numărul cardinal este numărul de vârfuri din grafic. $\Gamma (V,E)$ $V(\Gamma )$ $v\in V(\Gamma )$ $E(\Gamma )$ $e\in E(\Gamma )$ $n=|V(\Gamma )|$

Vârfurile adiacente ale graficului sunt vârfuri și astfel încât sau, cu alte cuvinte, ambele vârfuri sunt terminale pentru o muchie. $\Gamma$ $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Matricea de adiacență pentru un grafic simplu este [1] o matrice de dimensiune în care: $\Gamma$ ${\mathbf A}$ $n\ ori n$

a_{i,j}={\begin{cases}1&:\,\left\{v_{i},v_{j}\right\}\in E(G),\\0&:\, \left\{v_{i},v_{j}\right\}\not E(G)\end{cases}}

adică elementul matricei este egal cu unu dacă vârfurile și sunt adiacente și egal cu zero dacă nu și . $a_{i,j}$ $v_{i}$ $v_{j}$ $a_{i,i}=0$

Pentru un pseudograf , un element este egal cu dublul numărului de bucle atașate unui vârf [2] . De asemenea, este posibil să numărați buclele o dată. Bucla orientată este luată în considerare o dată [2] . $a_{i,i)$ $v_{i}$

Pentru un multigraf , un element este egal cu numărul de muchii multiple . $a_{i,j}$ $e=\stanga\{v_{i},v_{j}\dreapta\}$

Polinomul caracteristic al unui grafic este polinomul caracteristic al matricei sale de adiacență : $P_{G}(\lambda )$ $det(\lambda \mathbf {I} -\mathbf {A} )=0$

P_{G}(\lambda )=\lambda ^{n}+c_{1}\lambda ^{n-1}+c_{2}\lambda ^{n-2}+c_{3}\ lambda ^{n-3}+\dots +c_{n}

Vectorul propriu al graficului este vectorul propriu al matricei de adiacență: ${\mathbf x}$

\mathbf {A} \mathbf {x} =\lambda \mathbf {x}

Definiții ale spectrului unui grafic

În [3] , spectrul unui grafic este definit ca setul de valori proprii ale polinomului caracteristic al graficului (sau valorile proprii ale graficului ), unde și multiplicitățile acestor numere $\lambda _{i}$ $\lambda _{0}\leqslant \lambda _{1}\leqslant \dots \leqslant \lambda _{s)$ $m(\lambda _{i})$

Spec(\Gamma)={\begin{pmatrix}\lambda _{0}&\lambda _{1}&\dots &\lambda _{s-1}\\m(\lambda _{0} )&m(\lambda _{1})&\dots &m(\lambda _{s-1})\end{pmatrix}}

În [4] , spectrul unui grafic este definit pur și simplu ca mulțime de valori proprii:

Sp(\Gamma)=\left[\lambda _{1},\,\lambda _{2},\,\dots,\,\lambda _{n}\right]

Proprietăți

Coeficienții polinomului caracteristic al graficului îndeplinesc condițiile [3] : $c_{i}$ $\Gamma$

$c_{1}=0$
$-c_{2}$ este numărul de muchii ale graficului $\Gamma$
$-c_{3}$ - există de două ori numărul de triunghiuri în grafic $\Gamma$

Note

↑ Biggs, 1993 , p. 7.
↑ 1 2 Cvetkovici, 1984 , p. zece.
↑ 1 2 Biggs, 1993 , p. opt.
↑ Cvetkovich, 1984 , p. unsprezece.

Literatură

Teoria algebrică a graficelor Biggs NL . — al 2-lea. - Cambridge University Press, 1993. - 205 p.

Cvetkovich D., Dub M., Sahs H. Spectre de grafice. Teorie și aplicare. - Kiev: Naukova Dumka, 1984. - 384 p.