PROFILPELAJAR.COM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

См. также

Примечания

↑ Collatz, L. and Sinogowitz, U. Spektren endlicher Grafen // Abh. Math. Sem. Univ. Hamburg. — 1957. — № 21. — С. 63–77.
↑ Weisstein, Eric W. Cospectral Graphs (англ.) на сайте Wolfram MathWorld.
↑ Haruo Hosoya, Umpei Nagashima, Sachiko Hyugaji. Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices // Journal of Chemical Information and Modeling. — 1994. — Т. 34, вып. 2. — С. 428—431. — doi:10.1021/ci00018a033.
↑ A. J. Schwenk. Almost All Trees are Cospectral // New Directions in the Theory of Graphs / F. Harary. — New York: Academic Press, 1973. — С. 275–307.
↑ Toshikazu Sunada. Riemannian coverings and isospectral manifolds // Ann. of Math. — 1985. — Т. 21. — С. 169—186.
↑ Hoory, Linial, Widgerson, 2006, Определение 2.1.
↑ Alon, Spencer, 2011.
↑ Hoory, Linial, Widgerson, 2006, Теорема 2.4.
↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectra of Graphs. — 1980.
↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev. Recent Results in the Theory of Graph Spectra. — 1988. — (Annals of Discrete mathematics). — ISBN 0-444-70361-6. Архивировано 5 ноября 2017 года.
↑ ¹ ² Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. Eigenspaces of Graphs. — 1997. — ISBN 0-521-57352-1.

Литература

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.