Спектр графа

Спектр графа (Шаблон:Lang-en) - это множество собственных значений матрицы смежности графа.

Спектр может быть определен как для простого графа, так и для орграфа, мультиграфа, псевдографа или псевдомультиграфа.

Определения

Пусть $\mathrm{\Gamma }(V,E)$ - граф, где $V(\mathrm{\Gamma })$ есть множество его вершин $v\in V(\mathrm{\Gamma })$, а $E(\mathrm{\Gamma })$ есть множество его ребер $e\in E(\mathrm{\Gamma })$. Кардинальное число $n=|V(\mathrm{\Gamma })|$ есть количество вершин графа.

Смежными вершинами графа $\mathrm{\Gamma }$ являются вершины $v_1$ и $v_2$ такие, что $\{v_1,v_2\}\in E(G)$ или, другими словами, обе вершины являются концевыми для одного ребра.

Матрица смежности для простого графа $\mathrm{\Gamma }$ есть Шаблон:Sfn матрица $𝐀$ размера $n\times n$ где:

$a_{i,j}=\{\begin{array}{cc}1& :\{v_i,v_j\}\in E(G),\\ 0& :\{v_i,v_j\}\notin E(G)\end{array}$,

то есть элемент матрицы $a_{i,j}$ равен единице, если вершины $v_i$ и $v_j$ смежны, и равен нулю, если нет, причем $a_{i,i}=0$.

Для псевдографа элемент $a_{i,i}$ равен удвоенному числу петель, присоединенных к вершине $v_i$Шаблон:Sfn. Также возможен однократный учет петель. Ориентированная петля учитывается однократноШаблон:Sfn.

Для мультиграфа элемент $a_{i,j}$ равен числу кратных ребер $e=\{v_i,v_j\}$.

Характеристический многочлен графа $P_G(\lambda )$ есть характеристический многочлен его матрицы смежности $det(\lambda 𝐈-𝐀)=0$:

$P_G(\lambda )={\lambda }^n+c_1{\lambda }^{n-1}+c_2{\lambda }^{n-2}+c_3{\lambda }^{n-3}+\dots +c_n$

Собственный вектор графа $𝐱$ есть собственный вектор матрицы смежности :

$𝐀𝐱=\lambda 𝐱$

Определения спектра графа

В работе Шаблон:Sfn спектр графа определен как множество собственных чисел ${\lambda }_i$ характеристического многочлена графа (или собственных чисел графа), где ${\lambda }_0⩽{\lambda }_1⩽\dots ⩽{\lambda }_s$ и кратностей этих чисел $m({\lambda }_i)$

$Spec(\mathrm{\Gamma })=\left(\begin{array}{cccc}{\lambda }_0& {\lambda }_1& \dots & {\lambda }_{s-1}\\ m({\lambda }_0)& m({\lambda }_1)& \dots & m({\lambda }_{s-1})\end{array}\right)$

В работе Шаблон:Sfn спектр графа определен просто как множество собственных чисел:

$Sp(\mathrm{\Gamma })=[{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n]$

Свойства

Коэффициенты $c_i$ характеристического многочлена графа $\mathrm{\Gamma }$ удовлетворяют условиямШаблон:Sfn:

• $c_1=0$
• $-c_2$ - есть число ребер графа $\mathrm{\Gamma }$
• $-c_3$ - есть удвоенное число треугольников графа $\mathrm{\Gamma }$

Литература

• Шаблон:Книга

• Шаблон:Книга