Спектр графа
(
англ.
graph spectrum
) - это множество собственных значений матрицы смежности графа.
Спектр может быть определен как для простого
графа
, так и для
орграфа
,
мультиграфа
,
псевдографа
или
псевдомультиграфа
.
Определения
Пусть
-
граф
, где
есть множество его вершин
, а
есть множество его ребер
. Кардинальное число
есть количество вершин графа.
Смежными вершинами графа
являются вершины
и
такие, что
или, другими словами, обе вершины являются концевыми для одного ребра.
Матрица смежности
для простого графа
есть
матрица
размера
где:
-
,
то есть элемент матрицы
равен единице, если вершины
и
смежны, и равен нулю, если нет, причем
.
Для
псевдографа
элемент
равен удвоенному числу петель, присоединенных к вершине
. Также возможен однократный учет петель. Ориентированная петля учитывается однократно
.
Для
мультиграфа
элемент
равен числу кратных ребер
.
Характеристический многочлен графа
есть
характеристический многочлен
его матрицы смежности
:
-
Собственный вектор графа
есть собственный вектор матрицы смежности :
-
Определения спектра графа
В работе
спектр графа определен как множество собственных чисел
характеристического многочлена графа (или
собственных чисел графа
), где
и кратностей этих чисел
-
В работе
спектр графа определен просто как множество собственных чисел:
-
Свойства
Коэффициенты
характеристического многочлена графа
удовлетворяют условиям
:
-
-
- есть число ребер графа
-
- есть удвоенное число треугольников графа
Примечания
-
, с. 7.
-
↑
, с. 10.
-
↑
, с. 8.
-
, с. 11.
Литература
-
Biggs N.L.
Algebraic Graph Theory
(англ.)
. — 2nd. — Cambridge University Press, 1993. — 205 p.
-
Цветкович Д., Дуб М., Захс Х.
Спектры графов. Теория и применение. — Киев: Наукова Думка, 1984. — 384 с.