Спектральная теория графов

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

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

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

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

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

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

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

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

Изоспектральные графы конструируются при помощи метода Сунада^[en][5].

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

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

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

Константа Чигера (или число Чигера, или изопериметрическое число) графа — это числовая мера того, что граф имеет «узкое горло». Константа Чигера как мера наличия «узкого горла» представляет большой интерес во многих областях. Например, при построении сильно связанных компьютерная сетей, тасовании карт и топологии низких размерностей^[en] (в частности, при изучении гиперболических 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}$^[6].

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

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

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

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

История

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

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

См. также

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

Примечания

Литература

• Shlomo Hoory, Nathan Linial and Avi Wigderson. Expander graphs and their applications // 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. Spectral Graph theory. — American Mathematical Society, 1992. — Т. 92. — 207 с. — (Cbms Regional Conference Series in Mathematics). — ISBN 978-0821803158.

Ссылки

• Dan Spielman. Spectral Graph Theory and its Applications  (неопр.) (2004).
• Daniel Spielman. Spectral Graph Theory and its Applications  (неопр.). — presented at FOCS 2007 Conference.
• Lu, Lincoln Spectral graph theory  (неопр.) (2009). Дата обращения: 23 ноября 2014. Архивировано из оригинала 5 марта 2012 года.
• Spectral Graph Theory page at COPPE/Federal University of Rio de Janeiro

Эта страница в последний раз была отредактирована 24 декабря 2023 в 03:28.