Grafspektrum

Ett grafspektrum är en uppsättning egenvärden för en grafs närliggande matris .

Spektrumet kan definieras för både en enkel graf och en digraf , multigraf , pseudograf eller pseudomultigraf .

Definitioner

Låt vara en graf där det finns en uppsättning av dess hörn och det finns en uppsättning av dess kanter . Kardinalnumret är antalet hörn i grafen. $\Gamma (V,E)$ $V(\Gamma )$ $v\in V(\Gamma )$ $E(\Gamma )$ $e\in E(\Gamma )$ $n=|V(\Gamma )|$

Grafens angränsande hörn är hörn och sådana att eller, med andra ord, båda hörnen är terminala för en kant. $\Gamma$ $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Närliggande matris för en enkel graf är [1] en matris med storlek där: $\Gamma$ ${\mathbf A}$ $n\ gånger 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 vill säga, matriselementet är lika med ett om hörnen och är intilliggande, och lika med noll om inte, och . $a_{i,j}$ $v_{i}$ $v_{j}$ $a_{i,i}=0$

För en pseudograf är ett element lika med dubbelt så många slingor som är fästa vid en vertex [2] . Det går även att räkna loopar en gång. Den orienterade slingan beaktas en gång [2] . ${\displaystyle a_{i,i))$ $v_{i}$

För en multigraf är ett element lika med antalet flera kanter . $a_{i,j}$ $e=\left\{v_{i},v_{j}\right\}$

Det karakteristiska polynomet i en graf är det karakteristiska polynomet för dess närliggande matris : $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}

Egenvektorn för grafen är egenvektorn för närliggande matris: ${\mathbf x}$

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

Definitioner av spektrumet för en graf

I [3] definieras grafens spektrum som uppsättningen egenvärden för grafens karakteristiska polynom (eller grafens egenvärden ), där och multipliciteten av dessa 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] definieras en grafs spektrum helt enkelt som en uppsättning egenvärden:

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

Egenskaper

Koefficienterna för det karakteristiska polynomet i grafen uppfyller villkoren [3] : $c_{i}$ $\Gamma$

$c_{1}=0$
${\displaystyle -c_{2))$ är antalet grafkanter $\Gamma$
${\displaystyle -c_{3))$ - det finns dubbelt så många trianglar i grafen $\Gamma$

Anteckningar

↑ Biggs, 1993 , sid. 7.
↑ 1 2 Cvetkovich, 1984 , sid. tio.
↑ 1 2 Biggs, 1993 , sid. åtta.
↑ Cvetkovich, 1984 , sid. elva.

Litteratur

Biggs NL Algebraisk grafteori . — 2:a. - Cambridge University Press, 1993. - 205 sid.

Cvetkovich D., Dub M., Sahs H. Spectra of graphs. Teori och tillämpning. - Kiev: Naukova Dumka, 1984. - 384 sid.