Спектральная теория графов — направление в теории графов , изучающее свойства графов , характеристических многочленов , собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа .

Неориентированный граф имеет симметричную матрицу смежности, а потому имеет вещественные собственные значения ( мультимножество которых называется спектр графа ) и полное множество собственных векторов .

В то время как матрица смежности графа зависит от нумерации вершин, его спектр является инвариантом графа .

Спектральная теория графов занимается также параметрами, которые определяются путём умножения собственных значений матриц, связанных с графом, таких, как число Колен де Вердьера .

Изоспектральные графы

Два графа называются или коспектральными, если матрицы смежности графов имеют одинаковые мультимножества собственных значений.

Изоспектральные графы не обязательно изоморфны , но изоморфные графы всегда изоспектральны. Минимальная пара неизоморфных коспектральных неориентированных графов — ${\displaystyle \{K_{1,4},C_{4}\cup K_{1}\}}$ , то есть звезда с пятью вершинами и объединение цикла с 4 вершинами и графа, состоящего из единственной вершины, что показали Коллац и Сингович в 1957 году. Наименьшая пара неизоморфных коспектральных полиэдральных графов — два эннеаэдра с восемью вершинами в каждом .

Почти все деревья имеют коспектральные им графы, то есть доля деревьев порядка ${\displaystyle n}$ , для каждого из которых существует коспектральный граф, стремится к 1 при росте ${\displaystyle n}$ .

Изоспектральные графы конструируются при помощи .

Неравенство Чигера

Знаменитое неравенство Чигера из римановой геометрии имеет дискретный аналог, использующий матрицу Кирхгофа. Возможно, это наиболее важная теорема в спектральной теории графов и один из самых полезных фактов в алгоритмических приложениях. Неравенство оценивает наименьший разрез графа посредством второго собственного значения матрицы Кирхгофа.

Константа Чигера

Константа Чигера (или число Чигера , или изопериметрическое число ) графа — это числовая мера того, что граф имеет «узкое горло». Константа Чигера как мера наличия «узкого горла» представляет большой интерес во многих областях. Например, при построении сильно связанных компьютерная сетей , тасовании карт и (в частности, при изучении гиперболических 3- многообразий ).

Формально, константа Чигера ${\displaystyle h(G)}$ графа ${\displaystyle G}$ с ${\displaystyle n}$ вершинами определяется как

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

где минимум берётся по всем непустым множествам ${\displaystyle S}$ максимум с ${\displaystyle n/2}$ вершинами и ${\displaystyle \partial (S)}$ — рёберная граница множества ${\displaystyle S}$ , то есть множество рёбер, имеющих в точности одну конечную вершину в ${\displaystyle S}$ .

Неравенство Чигера

Если граф ${\displaystyle G}$ является ${\displaystyle d}$ -регулярным, существует связь между ${\displaystyle h(G)}$ и спектральным промежутком ${\displaystyle d-\lambda _{2}}$ графа ${\displaystyle G}$ . Неравенство Чигера исследовали Таннер, Алон и Мильман . Неравенство утверждает, что

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

Это неравенство тесно связано с ^* для цепей Маркова и его можно рассматривать как дискретную версию неравентства Чигера в римановой геометрии .

История

Спектральная теория графов возникла в 1950—1960 годах. Монография 1980 года « Спектры графов » ( Spectra of Graphs ) Цветковича, Дооба и Сакса (Cvetković, Michael Doob, Sachs) обобщила почти все исследования в этой области, известные к тому моменту. В 1988 году вышло обновлённое обозрение « Последние исследования в теории спектра графа » . Третье издание книги « Спектры графов » (1995) содержит итоги дальнейших вкладов в этой области .

Кроме теоретических исследований о связи структурных и спектральных свойств графов, другим источником стали исследования в квантовой химии , но связь этих двух направлений выяснена много позже .

См. также

• Алгебраическая связность
• Алгебраическая теория графов
• Спектральная кластеризация
• Топологическая теория графов
• Число Ловаса
• Экспандер

Примечания

Литература

• Shlomo Hoory, Nathan Linial and Avi Wigderson. // Bull. Amer. Math. Soc. — 2006. — № 43 . — С. 439—561 .
• Noga Alon, Joel H. Spencer. The Probabilistic Method. — 3rd Edition. — Hoboken, New Jersey: Wiley-Interscience, 2011. — 376 с. — ISBN 978-0470170205 .
• Fan Chung. . — American Mathematical Society, 1992. — Т. 92. — 207 с. — (Cbms Regional Conference Series in Mathematics). — ISBN 978-0821803158 .

Ссылки

• Dan Spielman. (неопр.) (2004).
• Daniel Spielman. (неопр.) . — presented at FOCS 2007 Conference.
• Lu, Lincoln (неопр.) (2009). Дата обращения: 23 ноября 2014. Архивировано из 5 марта 2012 года.