Graf spektrum

Et grafspektrum er et sæt egenværdier af en grafs tilstødende matrix .

Spektret kan defineres for både en simpel graf og en digraf , multigraf , pseudograf eller pseudomultigraf .

Definitioner

Lad være en graf, hvor der er et sæt af dens hjørner , og der er et sæt af dens kanter . Kardinaltallet er antallet af hjørner i grafen. $\Gamma (V,E)$ $V(\Gamma )$ $v\in V(\Gamma )$ $E(\Gamma )$ $e\in E(\Gamma )$ $n=|V(\Gamma )|$

De tilstødende hjørner af grafen er spidser og sådan, at eller med andre ord begge spidser er terminale for den ene kant. $\Gamma$ $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Adjacency-matrixen for en simpel graf er [1] en matrix af størrelse hvor: $\Gamma$ ${\mathbf A}$ $n\ gange n$

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

det vil sige, at matrixelementet er lig med én, hvis hjørnerne og er tilstødende, og lig med nul, hvis ikke, og . $a_{i,j}$ $v_{i}$ $v_{j}$ $a_{i,i}=0$

For en pseudograf er et element lig med det dobbelte af antallet af sløjfer knyttet til et toppunkt [2] . Det er også muligt at tælle sløjfer én gang. Den orienterede sløjfe tages i betragtning én gang [2] . ${\displaystyle a_{i,i))$ $v_{i}$

For en multigraf er et element lig med antallet af flere kanter . $a_{i,j}$ $e=\left\{v_{i},v_{j}\right\}$

Det karakteristiske polynomium i en graf er det karakteristiske polynomium for dens tilstødende matrix : $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}

Grafens egenvektor er egenvektoren for tilstødende matrix: ${\mathbf x}$

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

Definitioner af spektret af en graf

I [3] er spektret af en graf defineret som sættet af egenværdier af grafens karakteristiske polynomium (eller egenværdier af grafen ), hvor og multipliciteten af disse tal $\lambda _{i}$ ${\displaystyle \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}}

I [4] er spektret af en graf simpelthen defineret som sættet af egenværdier:

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

Egenskaber

Koefficienterne for det karakteristiske polynomium i grafen opfylder betingelserne [3] : $c_{i}$ $\Gamma$

$c_{1}=0$
$-c_{2}$ er antallet af grafkanter $\Gamma$
$-c_{3}$ - der er dobbelt så mange trekanter i grafen $\Gamma$

Noter

↑ Biggs, 1993 , s. 7.
↑ 1 2 Cvetkovich, 1984 , s. ti.
↑ 1 2 Biggs, 1993 , s. otte.
↑ Cvetkovich, 1984 , s. elleve.

Litteratur

Biggs NL Algebraisk grafteori . — 2. - Cambridge University Press, 1993. - 205 s.

Cvetkovich D., Dub M., Sahs H. Spektra af grafer. Teori og anvendelse. - Kiev: Naukova Dumka, 1984. - 384 s.