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

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

Неорієнтований граф

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

Тоді як матриця суміжності графу залежить від нумерації вершин, його спектр є інваріантом графу.

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

Ізоспектральні графи

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

Ізоспектральні графи не обов'язково ізоморфні, але ізоморфні графи завжди ізоспектральні. Мінімальна пара неізоморфних коспектральних неорієнтованих графів — , тобто зірка з п'ятьма вершинами і об'єднання циклу з 4 вершинами і графу, що складається з єдиної вершини, що показали Коллац і Сінговіч 1957 року. Найменша пара неізоморфних коспектральних поліедральних графів — два еннеаедри з вісьмома вершинами в кожному.

Майже всі дерева коспектральні, тобто частка коспектральних дерев з n вершинами прямує до 1 при зростанні n.

Ізоспектральні графи конструюють за допомогою методу Сунада.

Нерівність Чігера

Знаменита нерівність Чіґера з ріманової геометрії має дискретний аналог, який використовує матрицю Кірхгофа. Можливо, це найважливіша теорема в спектральній теорії графів і один з найкорисніших фактів у алгоритмічних застосуваннях. Нерівність оцінює найменший розріз графу за допомогою другого власного значення матриці Кірхгофа.

Стала Чіґера

Стала Чіґера (або число Чіґера) графа — це числова міра того, що граф має «вузьке місце». Стала Чіґера як міра наявності «вузького місця» становить великий інтерес у багатьох галузях, наприклад, під час побудови сильно зв'язаних комп'ютерних мереж, тасуванні карт і топології низьких розмірностей^[en] (зокрема, під час вивчення гіперболічних 3-многовидів).

Формально, стала Чіґера h(G) графу G з n вершинами визначається, як

:  

де мінімум береться за всіма непорожніми множинами S з максимум n/2 вершинами і ∂ (S) — реберна межа множини S, тобто множина ребер, що мають рівно одну кінцеву вершину в S.

Нерівність Чіґера

Якщо граф G є d-регулярним, існує зв'язок між h(G) і спектральним проміжком d — λ2 графу G. Нерівність Чіґера досліджували Таннер, Алон і Мільман. Нерівність стверджує, що:

:  

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

Історичний нарис

Спектральна теорія графів виникла в 1950-60-х роках. Крім теоретичних досліджень графів про зв'язок структурних і спектральних властивостей графів, іншим джерелом стали дослідження в квантовій хімії, але зв'язок цих двох напрямків з'ясовано значно пізніше. Монографія 1980 року «Спектри графів» (Spectra of Graphs) Цвєтковича, Дооба і Сакса (Cvetković, Michael Doob, Sachs) узагальнила майже всі дослідження в цій галузі, відомі на той час. 1988 року вийшов оновлений огляд «Останні дослідження в теорії спектра графу». Третє видання книги «Спектри графів» (1995) містить підсумки подальших робіт у цій галузі.

Див. також

• Алгебрична зв'язність
• Алгебрична теорія графів
• Спектральна кластеризація
• Індекс Естрада^[en]
• Число Ловаса^[ru]
• Збільшувач (теорія графів)
• Квантовий граф

Примітки

1. Collatz, L. and Sinogowitz, U. Spektren endlicher Grafen // Abh. Math. Sem. Univ. Hamburg. — 1957. — № 21. — С. 63–77.
2. Weisstein, Eric W. Cospectral Graphs(англ.) на сайті Wolfram MathWorld.
3. 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.
4. A. J. Schwenk. Almost All Trees are Cospectral // New Directions in the Theory of Graphs / F. Harary. — New York : Academic Press, 1973. — С. 275–307.
5. Toshikazu Sunada. Riemannian coverings and isospectral manifolds // Ann. of Math. — 1985. — Т. 21. — С. 169—186.
6. Hoory, Linial, Widgerson, 2006, Определение 2.1.
7. Alon, Spencer, 2011.
8. Hoory, Linial, Widgerson, 2006, Теорема 2.4.
9. Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. Eigenspaces of Graphs. — 1997. — ISBN 0-521-57352-1.
10. Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectra of Graphs. — 1980.
11. 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.

Література

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 (2004). . Архів оригіналу за 31 серпня 2021. Процитовано 31 серпня 2021. 
• Daniel Spielman. Spectral Graph Theory and its Applications. — presented at FOCS 2007 Conference.^{[недоступне посилання з липня 2019]}
• Lu, Lincoln Spectral graph theory (2009).^{[недоступне посилання з липня 2019]}
• Spectral Graph Theory page at COPPE/Federal University of Rio de Janeiro^{[недоступне посилання з липня 2019]}