У математиці спектральна теорія графів — це вивчення властивостей графів характеристичних многочленів, власних векторів і власних значень матриць, пов'язаних з графом, таких, як його матриця суміжності або матриця Кірхгофа.
Неорієнтований граф має симетричну матрицю суміжності, а тому має дійсні власні значення (мультимножина яких називається спектром графу) і повну множину власних векторів.
Тоді як матриця суміжності графу залежить від нумерації вершин, його спектр є інваріантом графу.
Спектральна теорія графів займається також параметрами, які визначають множенням власних значень матриць, пов'язаних з графом, таких, як число Колен де Вердьєра.
Два графи називають ізоспектральними[en] або коспектральними, якщо матриці суміжності графів мають однакові мультимножини власних значень.
Ізоспектральні графи не обов'язково ізоморфні, але ізоморфні графи завжди ізоспектральні. Мінімальна пара неізоморфних коспектральних неорієнтованих графів — { K 1 , 4 , C 4 ∪ ∪ --> K 1 } {\displaystyle \{K_{1,4},C_{4}\cup K_{1}\}} , тобто зірка з п'ятьма вершинами і об'єднання циклу з 4 вершинами і графу, що складається з єдиної вершини, що показали Коллац і Сінговіч[1][2] 1957 року. Найменша пара неізоморфних коспектральних поліедральних графів — два еннеаедри з вісьмома вершинами в кожному[3].
Майже всі дерева коспектральні, тобто частка коспектральних дерев з n вершинами прямує до 1 при зростанні n[4].
Ізоспектральні графи конструюють за допомогою методу Сунада[5].
Знаменита нерівність Чіґера з ріманової геометрії має дискретний аналог, який використовує матрицю Кірхгофа. Можливо, це найважливіша теорема в спектральній теорії графів і один з найкорисніших фактів у алгоритмічних застосуваннях. Нерівність оцінює найменший розріз графу за допомогою другого власного значення матриці Кірхгофа.
Стала Чіґера (або число Чіґера) графа — це числова міра того, що граф має «вузьке місце». Стала Чіґера як міра наявності «вузького місця» становить великий інтерес у багатьох галузях, наприклад, під час побудови сильно зв'язаних комп'ютерних мереж, тасуванні карт і топології низьких розмірностей[en] (зокрема, під час вивчення гіперболічних 3-многовидів).
Формально, стала Чіґера h(G) графу G з n вершинами визначається, як
: h ( G ) = min 0 < | S | ≤ ≤ --> n 2 | ∂ ∂ --> ( S ) | | S | , {\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}
де мінімум береться за всіма непорожніми множинами S з максимум n/2 вершинами і ∂ (S) — реберна межа множини S, тобто множина ребер, що мають рівно одну кінцеву вершину в S[6].
Якщо граф G є d-регулярним, існує зв'язок між h(G) і спектральним проміжком d — λ2 графу G. Нерівність Чіґера досліджували Таннер, Алон і Мільман[7]. Нерівність стверджує, що[8]:
: 1 2 ( d − − --> λ λ --> 2 ) ≤ ≤ --> h ( G ) ≤ ≤ --> 2 d ( d − − --> λ λ --> 2 ) . {\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}
Ця нерівність тісно пов'язана з границею границею Чіґера[en] для ланцюгів Маркова і її можна розглядати як дискретну версію нерівності Чіґера в рімановій геометрії.
Спектральна теорія графів виникла в 1950-60-х роках. Крім теоретичних досліджень графів про зв'язок структурних і спектральних властивостей графів, іншим джерелом стали дослідження в квантовій хімії, але зв'язок цих двох напрямків з'ясовано значно пізніше[9]. Монографія 1980 року «Спектри графів» (Spectra of Graphs)[10] Цвєтковича, Дооба і Сакса (Cvetković, Michael Doob, Sachs) узагальнила майже всі дослідження в цій галузі, відомі на той час. 1988 року вийшов оновлений огляд «Останні дослідження в теорії спектра графу»[11]. Третє видання книги «Спектри графів» (1995) містить підсумки подальших робіт у цій галузі[9].
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
Lokasi Pengunjung: 3.142.40.44