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

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

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

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

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

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

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

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

Ізоспектральні графи не обов'язково ізоморфні, але ізоморфні графи завжди ізоспектральні. Мінімальна пара неізоморфних коспектральних неорієнтованих графів — $\{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 вершинами і ∂ (S) — реберна межа множини S, тобто множина ребер, що мають рівно одну кінцеву вершину в S[6].

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

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

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

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

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

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

Див. також

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

Примітки

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š Cvetković, Peter Rowlinson, Slobodan Simić. Eigenspaces of Graphs. — 1997. — ISBN 0-521-57352-1.
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.

Література

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.
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]}

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

[FOOTNOTEHoory,_Linial,_Widgerson2006Определение_2.1-6] Hoory, Linial, Widgerson, 2006, Определение 2.1.

[FOOTNOTEAlon,_Spencer2011-7] Alon, Spencer, 2011.

[FOOTNOTEHoory,_Linial,_Widgerson2006Теорема_2.4-8] Hoory, Linial, Widgerson, 2006, Теорема 2.4.

[cvet2-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.