Спектр графа

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

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

Определения

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

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

Матрица смежности для простого графа $\Gamma$ есть матрица $\mathbf {A}$ размера $n\times 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}}$,

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

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

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

Характеристический многочлен графа $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}$

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

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

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

В работе спектр графа определен как множество собственных чисел $\lambda _{i}$ характеристического многочлена графа (или собственных чисел графа), где $\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}}$

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

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

Свойства

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

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

Литература

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

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