Русская Википедия:Спектр графа
Спектр графа (Шаблон:Lang-en) - это множество собственных значений матрицы смежности графа.
Спектр может быть определен как для простого графа, так и для орграфа, мультиграфа, псевдографа или псевдомультиграфа.
Определения
Пусть <math>\Gamma(V,E)</math> - граф, где <math>V(\Gamma)</math> есть множество его вершин <math>v \in V(\Gamma)</math>, а <math>E(\Gamma)</math> есть множество его ребер <math>e \in E(\Gamma)</math>. Кардинальное число <math>n=|V(\Gamma)|</math> есть количество вершин графа.
Смежными вершинами графа <math>\Gamma</math> являются вершины <math>v_1</math> и <math>v_2</math> такие, что <math>\left \{v_1, v_2 \right \} \in E(G)</math> или, другими словами, обе вершины являются концевыми для одного ребра.
Матрица смежности для простого графа <math>\Gamma</math> есть Шаблон:Sfn матрица <math>\mathbf A</math> размера <math>n \times n</math> где:
- <math> 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} </math>,
то есть элемент матрицы <math>a_{i,j}</math> равен единице, если вершины <math>v_i</math> и <math>v_j</math> смежны, и равен нулю, если нет, причем <math>a_{i,i}=0</math>.
Для псевдографа элемент <math>a_{i,i}</math> равен удвоенному числу петель, присоединенных к вершине <math>v_i</math>Шаблон:Sfn. Также возможен однократный учет петель. Ориентированная петля учитывается однократноШаблон:Sfn.
Для мультиграфа элемент <math>a_{i,j}</math> равен числу кратных ребер <math>e= \left \{ v_i, v_j \right \}</math>.
Характеристический многочлен графа <math>P_G(\lambda)</math> есть характеристический многочлен его матрицы смежности <math>det(\lambda \mathbf I -\mathbf A)=0</math>:
- <math>P_G(\lambda) = \lambda^n + c_1 \lambda^{n-1}+ c_2 \lambda^{n-2} +c_3 \lambda^{n-3} + \dots + c_n </math>
Собственный вектор графа <math>\mathbf x</math> есть собственный вектор матрицы смежности :
- <math>\mathbf A \mathbf x = \lambda \mathbf x</math>
Определения спектра графа
В работе Шаблон:Sfn спектр графа определен как множество собственных чисел <math>\lambda_i</math> характеристического многочлена графа (или собственных чисел графа), где <math>\lambda_0 \leqslant \lambda_1 \leqslant \dots \leqslant \lambda_s</math> и кратностей этих чисел <math>m(\lambda_i)</math>
- <math>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} </math>
В работе Шаблон:Sfn спектр графа определен просто как множество собственных чисел:
- <math>Sp(\Gamma)= \left [ \lambda_1 , \, \lambda_2 , \, \dots , \, \lambda_n \right ]</math>
Свойства
Коэффициенты <math>c_i</math> характеристического многочлена графа <math>\Gamma</math> удовлетворяют условиямШаблон:Sfn:
- <math>c_1 = 0 </math>
- <math>-c_2 </math> - есть число ребер графа <math>\Gamma</math>
- <math>-c_3</math> - есть удвоенное число треугольников графа <math>\Gamma</math>
Примечания
Литература
