Спектр графа

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

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

Определения

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

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

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

,

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

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

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

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

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

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

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

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

Свойства

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

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

Примечания

Литература

  • Biggs N.L. Algebraic Graph Theory (англ.). — 2nd. — Cambridge University Press, 1993. — 205 p.
  • Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. — Киев: Наукова Думка, 1984. — 384 с.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.