Введение
Аспекты линейной алгебры в теории графов. В математике спектральная теория графов изучает свойства графа в связи с характеристическим многочленом, собственными значениями и собственными векторами матриц, связанных с графом, таких как матрица смежности или матрица Лапласа. Матрица смежности простого неориентированного графа является вещественной симметричной матрицей и, следовательно, ортогонально диагонализуема; её собственные значения являются вещественными алгебраическими целыми числами. Хотя матрица смежности зависит от нумерации вершин, её спектр является инвариантом графа, хотя и не полным. Спектральная теория графов также рассматривает графовые параметры, определяемые через кратности собственных значений матриц, связанных с графом, такие как число Колина де Вердьера.
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number.
Коспектральные графики
Два графа называются коспектральными или изоспектральными, если матрицы смежности этих графов являются изоспектральными, то есть если матрицы смежности имеют одинаковые мультимножества собственных значений. Коспектральные графы не обязаны быть изоморфными, но изоморфные графы всегда являются коспектральными.
Коспектральные партнеры
Пара графов называется коспектральными партнерами, если они имеют один и тот же спектр, но неизоморфны. Наименьшая пара коспектральных партнеров — {K1,4, C4 ∪ K1}, состоящая из звезды на 5 вершинах и объединения графа цикла на 4 вершины с графом на одну вершину, как было сообщено Коллатцем и Синогуицем в 1957 году. Наименьшая пара полиэдрических коспектральных партнеров — это энеаэдры с восемью вершинами каждая.
Поиск коспектральных графиков
Почти все деревья являются коспектральными, то есть при увеличении числа вершин доля деревьев, для которых существует коспектральное дерево, стремится к 1. Пара регулярных графов коспектральна тогда и только тогда, когда их дополнения коспектральны. Пара дистанционно-регулярных графов коспектральна тогда и только тогда, когда у них одинаковый массив пересечений. Коспектральные графы также могут быть построены с помощью метода Сунады. Другим важным источником коспектральных графов являются графики коллинеарности точек и графики пересечения прямых в точечных геометриях. Эти графы всегда коспектральны, но часто неизоморфны.
Неравенство Чигера
Знаменитое неравенство Чигера из римановой геометрии имеет дискретный аналог, связанный с матрицей Лапласа; это, пожалуй, самая важная теорема в спектральной теории графов и один из наиболее полезных фактов в алгоритмических задачах. Оно позволяет приближенно находить минимальный разрез графа, используя второе собственное значение его лапласиана.