Gráf spektrum

A gráfspektrum egy gráf szomszédsági mátrixának sajátértékeinek halmaza .

A spektrum megadható egyszerű gráfhoz és digráfhoz , multigráfhoz , pszeudográfhoz vagy pszeudomultigráfhoz is .

Definíciók

Legyen egy gráf , ahol van egy halmaz a csúcsaiból és van egy halmaz az éleiből . A kardinális szám a gráf csúcsainak száma. $\Gamma (V,E)$ $V(\Gamma )$ $v\in V(\Gamma )$ $E(\Gamma )$ $e\in E(\Gamma )$ $n=|V(\Gamma )|$

A gráf szomszédos csúcsai olyan csúcsok , amelyek vagy más szóval mindkét csúcs egy élhez terminális. $\Gamma$ $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Egy egyszerű gráf szomszédsági mátrixa [ 1] egy méretű mátrix , ahol: $\Gamma$ ${\mathbf A}$ $n\szer 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}}

vagyis a mátrixelem egyenlő eggyel, ha a és csúcsok szomszédosak, és egyenlő nullával, ha nem, és . $a_{i,j}$ $v_{i}$ $v_{j}$ $a_{i,i}=0$

Egy pszeudográf esetében egy elem egyenlő a csúcshoz kapcsolódó hurkok számának kétszeresével [2] . A hurkok egyszeri megszámlálására is van lehetőség. Az orientált hurkot egyszer vesszük figyelembe [2] . ${\displaystyle a_{i,i))$ $v_{i}$

Multigráf esetén egy elem egyenlő a többszörös élek számával . $a_{i,j}$ $e=\left\{v_{i},v_{j}\right\}$

Egy gráf karakterisztikus polinomja a szomszédsági mátrixának karakterisztikus polinomja : $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}+\pontok +c_{n}

A gráf sajátvektora a szomszédsági mátrix sajátvektora: ${\mathbf x}$

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

Egy gráf spektrumának definíciói

A [3] -ban a gráf spektruma a gráf karakterisztikus polinomjának sajátértékeinek halmaza (vagy a gráf sajátértékei ), ahol és ezeknek a számoknak a többszörösei $\lambda _{i}$ ${\displaystyle \lambda _{0}\leqslant \lambda _{1}\leqslant \dots \leqslant \lambda _{s))$ $m(\lambda _{i})$

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

A [4]-ben a gráf spektruma egyszerűen a sajátértékek halmazaként van definiálva:

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

Tulajdonságok

A gráf karakterisztikus polinomjának együtthatói teljesítik a feltételeket [3] : $c_{i}$ $\Gamma$

$c_{1}=0$
${\displaystyle -c_{2))$ a gráf éleinek száma $\Gamma$
${\displaystyle -c_{3))$ - kétszer annyi háromszög van a grafikonon $\Gamma$

Jegyzetek

↑ Biggs, 1993 , p. 7.
↑ 1 2 Cvetkovich, 1984 , p. tíz.
↑ 1 2 Biggs, 1993 , p. nyolc.
↑ Cvetkovich, 1984 , p. tizenegy.

Irodalom

Biggs NL algebrai gráfelmélet . — 2. - Cambridge University Press, 1993. - 205 p.

Cvetkovich D., Dub M., Sahs H. Grafikonok spektruma. Elmélet és alkalmazás. - Kijev: Naukova Dumka, 1984. - 384 p.