Спектр графа

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

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

ОпределенияПравить

Пусть   - граф, где   есть множество его вершин  , а   есть множество его ребер  . Кардинальное число   есть количество вершин графа.

Смежными вершинами графа   являются вершины   и   такие, что   или, другими словами, обе вершины являются концевыми для одного ребра.

Матрица смежности для простого графа   есть [1] матрица   размера   где:

 ,

то есть элемент матрицы   равен единице, если вершины   и   смежны, и равен нулю, если нет, причем  .

Для псевдографа элемент   равен удвоенному числу петель, присоединенных к вершине  [2]. Также возможен однократный учет петель. Ориентированная петля учитывается однократно[2].

Для мультиграфа элемент   равен числу кратных ребер  .

Характеристический многочлен графа   есть характеристический многочлен его матрицы смежности  :

 

Собственный вектор графа   есть собственный вектор матрицы смежности :

 

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

В работе [3] спектр графа определен как множество собственных чисел   характеристического многочлена графа (или собственных чисел графа), где   и кратностей этих чисел  

 

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

 

СвойстваПравить

Коэффициенты   характеристического многочлена графа   удовлетворяют условиям[3]:

  •  
  •   - есть число ребер графа  
  •   - есть удвоенное число треугольников графа  

ПримечанияПравить

ЛитератураПравить

  • Biggs N.L. Algebraic Graph Theory (англ.). — 2nd. — Cambridge University Press, 1993. — 205 p.
  • Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. — Киев: Наукова Думка, 1984. — 384 с.