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

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

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

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

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

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

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

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

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

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

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

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

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

Стала Чіґера

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

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). Spectral Graph Theory and its Applications. Архів оригіналу за 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]}