Спектр графа

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

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

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

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

Матрица смежности для простого графа ${\displaystyle \Gamma }$ есть ^[1] матрица ${\displaystyle \mathbf {A} }$ размера ${\displaystyle n\times n}$ где:

${\displaystyle 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}}}$,

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

Для псевдографа элемент ${\displaystyle a_{i,i}}$ равен удвоенному числу петель, присоединенных к вершине ${\displaystyle v_{i}}$^[2]. Также возможен однократный учет петель. Ориентированная петля учитывается однократно^[2].

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

Характеристический многочлен графа ${\displaystyle P_{G}(\lambda )}$ есть характеристический многочлен его матрицы смежности ${\displaystyle det(\lambda \mathbf {I} -\mathbf {A} )=0}$:

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

Собственный вектор графа ${\displaystyle \mathbf {x} }$ есть собственный вектор матрицы смежности :

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

В работе ^[3] спектр графа определен как множество собственных чисел ${\displaystyle \lambda _{i}}$ характеристического многочлена графа (или собственных чисел графа), где ${\displaystyle \lambda _{0}\leqslant \lambda _{1}\leqslant \dots \leqslant \lambda _{s}}$ и кратностей этих чисел ${\displaystyle m(\lambda _{i})}$

${\displaystyle 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}}}$

В работе ^[4] спектр графа определен просто как множество собственных чисел:

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

Коэффициенты ${\displaystyle c_{i}}$ характеристического многочлена графа ${\displaystyle \Gamma }$ удовлетворяют условиям^[3]:

• ${\displaystyle c_{1}=0}$
• ${\displaystyle -c_{2}}$ - есть число ребер графа ${\displaystyle \Gamma }$
• ${\displaystyle -c_{3}}$ - есть удвоенное число треугольников графа ${\displaystyle \Gamma }$

• Biggs N.L. Algebraic Graph Theory (англ.). — 2nd. — Cambridge University Press, 1993. — 205 p.

• Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. — Киев: Наукова Думка, 1984. — 384 с.