Спектр графа

Пусть ${\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} }$

Коэффициенты ${\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 с.