Loading AI tools
Из Википедии, свободной энциклопедии
Спектр графа (англ. graph spectrum) - это множество собственных значений матрицы смежности графа.
Спектр может быть определен как для простого графа, так и для орграфа, мультиграфа, псевдографа или псевдомультиграфа.
Пусть - граф, где есть множество его вершин , а есть множество его ребер . Кардинальное число есть количество вершин графа.
Смежными вершинами графа являются вершины и такие, что или, другими словами, обе вершины являются концевыми для одного ребра.
Матрица смежности для простого графа есть [1] матрица размера где:
то есть элемент матрицы равен единице, если вершины и смежны, и равен нулю, если нет, причем .
Для псевдографа элемент равен удвоенному числу петель, присоединенных к вершине [2]. Также возможен однократный учет петель. Ориентированная петля учитывается однократно[2].
Для мультиграфа элемент равен числу кратных ребер .
Характеристический многочлен графа есть характеристический многочлен его матрицы смежности :
Собственный вектор графа есть собственный вектор матрицы смежности :
В работе [3] спектр графа определен как множество собственных чисел характеристического многочлена графа (или собственных чисел графа), где и кратностей этих чисел
В работе [4] спектр графа определен просто как множество собственных чисел:
Коэффициенты характеристического многочлена графа удовлетворяют условиям[3]:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.