Спектр графа () - это множество собственных значений матрицы смежности графа.
Спектр может быть определен как для простого графа, так и для орграфа, мультиграфа, псевдографа или псевдомультиграфа.
Определения Пусть - граф, где есть множество его вершин , а есть множество его ребер . Кардинальное число есть количество вершин графа.
Смежными вершинами графа являются вершины и такие, что или, другими словами, обе вершины являются концевыми для одного ребра.
Матрица смежности для простого графа есть матрица размера где: ,
то есть элемент матрицы равен единице, если вершины и смежны, и равен нулю, если нет, причем .
Для псевдографа элемент равен удвоенному числу петель, присоединенных к вершине . Также возможен однократный учет петель. Ориентированная петля учитывается однократно.
Для мультиграфа элемент равен числу кратных ребер .
Характеристический многочлен графа есть характеристический многочлен его матрицы смежности :
Собственный вектор графа есть собственный вектор матрицы смежности :
Определения спектра графа
В работе спектр графа определен как множество собственных чисел характеристического многочлена графа (или собственных чисел графа), где и кратностей этих чисел
В работе спектр графа определен просто как множество собственных чисел:
Свойства
Коэффициенты характеристического многочлена графа удовлетворяют условиям:
- есть число ребер графа - есть удвоенное число треугольников графа
Примечания
Литература
Категория:Алгебраическая теория графов