Перегляд вихідного коду сторінки Спектральна теорія графів

У математиці '''спектральна теорія графів'''&nbsp;— це вивчення властивостей [[Граф (математика)|графів]] [[Характеристичний поліном|характеристичних многочленів]], [[Власні вектори та власні значення|власних векторів і власних значень]] матриць, пов'язаних з графом, таких, як його [[матриця суміжності]] або [[матриця Кірхгофа]].

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

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

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

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

== Ізоспектральні графи ==
Два графи називають {{Нп|Ізоспектральні оператори|ізоспектральними|en|Isospectral}} або '''коспектральними''', якщо матриці суміжності графів мають однакові мультимножини власних значень.

Ізоспектральні графи не обов'язково ізоморфні, але ізоморфні графи завжди ізоспектральні. Мінімальна пара неізоморфних коспектральних неорієнтованих графів&nbsp;— <math>\{K_{1,4}, C_4 \cup K_1\}</math>, тобто зірка з п'ятьма вершинами і об'єднання циклу з 4 вершинами і графу, що складається з єдиної вершини, що показали Коллац і Сінговіч<ref>{{статья|автор=Collatz, L. and Sinogowitz, U.|заглавие=Spektren endlicher Grafen|ссылка=|язык=|издание=Abh. Math. Sem. Univ. Hamburg|тип=|год=1957|том=|номер=21|страницы=63–77|doi=|issn=}}</ref><ref>{{mathworld|CospectralGraphs|Cospectral Graphs}}</ref> 1957 року. Найменша пара неізоморфних коспектральних [[Багатогранний граф|поліедральних графів]]&nbsp;— два [[Дев'ятигранник|еннеаедри]] з вісьмома вершинами в кожному<ref>{{статья|автор=Haruo Hosoya, Umpei Nagashima, Sachiko Hyugaji|doi=10.1021/ci00018a033|выпуск=2|издание=Journal of Chemical Information and Modeling|страницы=428—431|заглавие=Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices|том=34|год=1994}}</ref>.

Майже всі дерева коспектральні, тобто частка коспектральних дерев з n вершинами прямує до 1 при зростанні n<ref>{{книга-ру
|автор = A. J. Schwenk
|заглавие = New Directions in the Theory of Graphs
|ответственный = F. Harary
|ссылка = 
|место = New York
|издательство = Academic Press
|год = 1973
|часть = Almost All Trees are Cospectral
|страниц = 
|страницы = 275–307
|isbn = 
|ref = 
}}</ref>.

Ізоспектральні графи конструюють за допомогою методу Сунада<ref>{{статья|автор=Toshikazu Sunada|издание=Ann. of Math|страницы=169—186|заглавие=Riemannian coverings and isospectral manifolds|том=21|год=1985}}</ref>.

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

=== Стала Чіґера ===
{{Докладніше|Стала Чіґера (теорія графів)}}
'''Стала Чіґера''' (або '''число Чіґера''') графа&nbsp;— це числова міра того, що граф має «вузьке місце». Стала Чіґера як міра наявності «вузького місця» становить великий інтерес у багатьох галузях, наприклад, під час побудови сильно зв'язаних комп'ютерних мереж, тасуванні карт і {{Нп|Геометрична топологія|топології низьких розмірностей|en|Geometric_topology#Low-dimensional_topology}} (зокрема, під час вивчення [[гіперболічна геометрія|гіперболічних]] 3-[[многовид]]ів).

Формально, стала Чіґера h(G) графу G з n вершинами визначається, як
 : <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|},</math>
де мінімум береться за всіма непорожніми множинами S з максимум n/2 вершинами і ∂ (S)&nbsp;— реберна межа множини S, тобто множина ребер, що мають рівно одну кінцеву вершину в S{{sfn|Hoory, Linial, Widgerson|2006|loc=Определение  2.1}}.

=== Нерівність Чіґера ===
Якщо граф G є d-регулярним, існує зв'язок між h(G) і спектральним проміжком d&nbsp;— λ2 графу G. Нерівність Чіґера досліджували Таннер, Алон і Мільман{{sfn|Alon, Spencer|2011}}. Нерівність стверджує, що{{sfn|Hoory, Linial, Widgerson|2006|loc=Теорема 2.4}}:
 : <math>\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>
Ця нерівність тісно пов'язана з границею {{не переведено 5|Границя Чіґера|границею Чіґера|en|Cheeger bound}} для ланцюгів Маркова і її можна розглядати як дискретну версію нерівності Чіґера в рімановій геометрії.

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

Спектральна теорія графів виникла в 1950-60-х роках. Крім теоретичних досліджень графів про зв'язок структурних і спектральних властивостей графів, іншим джерелом стали дослідження в квантовій хімії, але зв'язок цих двох напрямків з'ясовано значно пізніше<ref name="cvet2">{{книга-ру
|автор = Dragoš Cvetković, Peter Rowlinson, Slobodan Simić
|заглавие = Eigenspaces of Graphs
|ответственный = 
|ссылка = 
|место = 
|издательство = 
|год = 1997
|том = 
|страниц = 
|страницы = 
|isbn = 0-521-57352-1
|ref = 
}}</ref>. Монографія 1980 року «Спектри графів» (Spectra of Graphs)<ref>{{книга-ру
|автор = Dragoš M. Cvetković, Michael Doob, Horst Sachs
|заглавие = Spectra of Graphs
|ответственный = 
|ссылка = 
|место = 
|издательство = 
|год = 1980
|том = 
|страниц = 
|страницы = 
|isbn = 
|ref = 
}}</ref> Цвєтковича, Дооба і Сакса (Cvetković, Michael Doob, Sachs) узагальнила майже всі дослідження в цій галузі, відомі на той час. 1988 року вийшов оновлений огляд «Останні дослідження в теорії спектра графу»<ref>{{книга-ру
|автор = Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev
|заглавие = Recent Results in the Theory of Graph Spectra
|серия = Annals of Discrete mathematics
|номер = 36
|год = 1988
|isbn = 0-444-70361-6
|ссылка = http://www.sciencedirect.com/science/bookseries/01675060/36
}}</ref>. Третє видання книги «Спектри графів» (1995) містить підсумки подальших робіт у цій галузі<ref name="cvet2" />.

== Див. також ==
* [[Алгебрична зв'язність]]
* [[Алгебрична теорія графів]]
* [[Спектральна кластеризація]]
* {{нп|Індекс Естрада||en|Estrada index}}
* {{нп|Число Ловаса||ru|}}
* [[Збільшувач (теорія графів)]]
* [[Квантовий граф]]

== Примітки ==
{{примітки|2}}

== Література ==
Shlomo Hoory, Nathan Linial and Avi Wigderson [[Expander graphs and their applications]] // Bull. Amer. Math. Soc.&nbsp;— 2006.&nbsp;— №&nbsp;43.&nbsp;— С. 439—561.
Noga Alon, Joel H. Spencer. The Probabilistic Method.&nbsp;— 3rd Edition.&nbsp;— Hoboken, New Jersey: Wiley-Interscience, 2011.&nbsp;— 376 с.&nbsp;— ISBN 978-0470170205.
Fan Chung. Spectral Graph theory.&nbsp;— American Mathematical Society, 1992.&nbsp;— Т. 92.&nbsp;— 207 с.&nbsp;— (Cbms Regional Conference Series in Mathematics).&nbsp;— ISBN 978-0821803158

== Посилання ==
* {{cite web|author=Dan Spielman|title=Spectral Graph Theory and its Applications|url=http://www.cs.yale.edu/homes/spielman/eigs/|year=2004|accessdate=31 серпня 2021|archive-date=31 серпня 2021|archive-url=https://web.archive.org/web/20210831152843/http://www.cs.yale.edu/homes/spielman/eigs/}}
* [http://Daniel%20Spielman.%20Spectral%20Graph%20Theory%20and%20its%20Applications.%20—%20presented%20at%20FOCS%202007%20Conference. Daniel Spielman. Spectral Graph Theory and its Applications.&nbsp;— presented at FOCS 2007 Conference.]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}
* [http://Lu,%20Lincoln%20Spectral%20graph%20theory%20(2009). Lu, Lincoln Spectral graph theory (2009).]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}
* [http://Spectral%20Graph%20Theory%20page%20at%20COPPE/Federal%20University%20of%20Rio%20de%20Janeiro Spectral Graph Theory page at COPPE/Federal University of Rio de Janeiro]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}
{{Бібліоінформація}}
{{Розділи математики}}
[[Категорія:Теорія графів]]
[[Категорія:Спектральна теорія]]