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

В математике — матриц , теория спектральных графов это изучение свойств графа по отношению к характеристическому многочлену , собственным значениям и собственным векторам связанных с графом, таких как его матрица смежности или матрица Лапласа .

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

Хотя матрица смежности зависит от маркировки вершин, ее спектр является инвариантом графа , хотя и не полным.

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

Коспектральные графики

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

Коспектральные графы не обязательно должны быть изоморфными , но изоморфные графы всегда коспектральны.

Графы, определяемые их спектром

График $G$ Говорят, что он определяется своим спектром, если любой другой граф с тем же спектром, что и $G$ изоморфен $G$ .

Некоторые первые примеры семейств графов, которые определяются их спектром, включают:

Полные графики .
Конечные звездообразные деревья .

Коспектральные сопряжения

Пара графов называется коспектрально сопряженной, если они имеют одинаковый спектр, но не изоморфны.

Наименьшая пара коспектральных сопряжений - это { K _1,4 , C ₄ ∪ K ₁ }, состоящая из 5-вершинной звезды и объединения графов 4-вершинного цикла и одновершинного графа, как сообщили Коллатц и Синоговитц. ^[1]^[2] в 1957 году.

Наименьшая пара многогранных коспектральных сопряжений — это эннеаэдры с восемью вершинами каждый. ^[3]

Нахождение коспектральных графов

Почти все деревья коспектральны, т. е. с ростом числа вершин доля деревьев, для которых существует коспектральное дерево, стремится к 1. ^[4]

Пара правильных графов коспектральна тогда и только тогда, когда их дополнения коспектральны. ^[5]

Пара дистанционно регулярных графов коспектральна тогда и только тогда, когда они имеют одинаковый массив пересечений.

Коспектральные графы можно построить также с помощью метода Сунады . ^[6]

Другим важным источником коспектральных графов являются графы коллинеарности точек и графы пересечения линий геометрий точка-линия . Эти графы всегда коспектральны, но часто неизоморфны. ^[7]

Неравенство Чигера

Знаменитое неравенство Чигера из римановой геометрии имеет дискретный аналог, включающий матрицу Лапласа; это, пожалуй, самая важная теорема теории спектральных графов и один из наиболее полезных фактов в алгоритмических приложениях. Он аппроксимирует самый разреженный разрез графа через второе собственное значение его лапласиана.

Константа Чигера

Константа Чигера (также число Чигера или изопериметрическое число ) графа является числовой мерой того, имеет ли график «узкое место» или нет. Константа Чигера как мера «узкого места» представляет большой интерес во многих областях: например, при построении хорошо связанных сетей компьютеров , перетасовке карт и низкомерной топологии (в частности, исследовании гиперболических 3- многообразий ).

Более формально, константа Чигера h ( G ) графа G на n вершинах определяется как

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

где минимум приходится на все непустые множества S, состоящие не более чем из n /2 вершин, а ∂( S ) — граница ребра , S множество ребер с ровно одной конечной точкой в S. т. е . ^[8]

Неравенство Чигера

Когда граф G является d существует связь между h ( G ) и спектральной щелью d − λ ₂ графа G. -регулярным , Неравенство Додзюка ^[9] и независимо Алон и Мильман ^[10] заявляет, что ^[11]

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

Это неравенство тесно связано с оценкой Чигера для цепей Маркова и может рассматриваться как дискретная версия неравенства Чигера в римановой геометрии .

Для общих связных графов, которые не обязательно являются регулярными, альтернативное неравенство дает Чанг. ^[12]^: 35

{\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},

где $\lambda$ — наименьшее нетривиальное собственное значение нормализованного лапласиана, а ${\mathbf {h} }(G)$ (нормированная) константа Чигера

{\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}

где ${\mathrm {vol} }(Y)$ представляет собой сумму степеней вершин в $Y$ .

Неравенство Хоффмана – Дельсарта.

Существует граница собственных значений для независимых множеств в регулярных графах , первоначально предложенная Аланом Дж. Хоффманом и Филиппом Дельсартом. ^[13]

Предположим, что $G$ это $k$ -регулярный график на $n$ вершины с наименьшим собственным значением $\lambda _{\mathrm {min} }$ . Затем: $\alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}$ где $\alpha (G)$ обозначает его число независимости .

Эта оценка применялась, например, для установления алгебраических доказательств теоремы Эрдеша–Ко–Радо и ее аналога для пересекающихся семейств подпространств над конечными полями . ^[14]

Для общих графов, которые не обязательно являются регулярными, аналогичную верхнюю оценку числа независимости можно получить, используя максимальное собственное значение $\lambda '_{max}$ нормированного лапласиана ^[12] из $G$ : $\alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}$ где ${\mathrm {maxdeg} }$ и ${\mathrm {mindeg} }$ обозначают максимальную и минимальную степень в $G$ , соответственно. Это следствие более общего неравенства (стр. 109 в ^[12]): ${\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G))$ где $X$ представляет собой независимый набор вершин и ${\mathrm {vol} }(Y)$ обозначает сумму степеней вершин в $Y$ .

Исторический очерк

Теория спектральных графов возникла в 1950-х и 1960-х годах. Помимо теоретико-графовых исследований взаимосвязи между структурными и спектральными свойствами графов, еще одним важным источником были исследования в области квантовой химии , но связи между этими двумя направлениями работы были обнаружены намного позже. ^[15] Монография 1980 года «Спектры графов». ^[16] Цветкович, Дуб и Сакс обобщили почти все исследования в этой области на сегодняшний день. В 1988 году он был дополнен обзором « Последние результаты в теории спектров графов» . ^[17] Третье издание «Спектров графов» (1995 г.) содержит краткое изложение дальнейших недавних вкладов в эту тему. ^[15] Дискретный геометрический анализ, созданный и развитый Тошиказу Сунадой в 2000-х годах, касается теории спектральных графов в терминах дискретных лапласианов, связанных с взвешенными графами. ^[18] и находит применение в различных областях, в том числе в анализе формы . В последние годы теория спектральных графов расширилась до графов с изменяющимися вершинами, которые часто встречаются во многих реальных приложениях. ^[19]^[20]^[21]^[22]

См. также

Ссылки

^ Коллатц, Л. и Синоговиц, У. «Спектры конечного числа». Деф. Гамбург 21, 63–77, 1957.
^ Вайсштейн, Эрик В. «Коспектральные графики» . Математический мир .
^ Хосоя, Харуо ; Нагашима, Умпей; Хьюгадзи, Сатико (1994), «Топологические графы-близнецы. Наименьшая пара изоспектральных многогранных графов с восемью вершинами», Journal of Chemical Information and Modeling , 34 (2): 428–431, doi : 10.1021/ci00018a033 .
^ Швенк (1973) , стр. 275–307.
^ Годсил, Крис (7 ноября 2007 г.). «Почти все ли графы коспектральны?» (PDF) .
^ Сунада, Тошикадзу (1985), "Римановы накрытия и изоспектральные многообразия", Ann. математики. , 121 (1): 169–186, номер документа : 10.2307/1971195 , JSTOR 1971195 .
^ Брауэр и Хэмерс, 2011 г.
^ Определение 2.1 в Hoory, Linial & Wigderson (2006).
^ Дж. Додзюк, Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий, Trans. амер. Математика. Соц. 284 (1984), вып. 2, 787–794.
^ Алон и Спенсер 2011 .
^ Теорема 2.4 в книге Хори, Линиала и Вигдерсона (2006).
^ Jump up to: ^а ^б ^с Чанг, Фан (1997). Американское математическое общество (ред.). Спектральная теория графов . Провиденс, Род-Айленд, ISBN 0821803158 . MR 1421568 [первые 4 главы доступны на сайте] {{cite book}}: CS1 maint: постскриптум ( ссылка )
^ Годсил, Крис (май 2009 г.). «Теоремы Эрдеша-Ко-Радо» (PDF) .
^ Годсил, CD; Мигер, Карен (2016). Теоремы Эрдеша-Ко-Радо: алгебраические подходы . Кембридж, Великобритания. ISBN 9781107128446 . OCLC 935456305 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Jump up to: ^а ^б Собственные пространства графов , Драгош Цветкович , Питер Роулинсон, Слободан Симич (1997) ISBN 0-521-57352-1
^ Драгош М. Цветкович, Майкл Дуб, Хорст Сакс , Спектры графов (1980)
^ Цветкович, Драгош М.; Дуб, Майкл; Гутман Иван; Торгасев, А. (1988). Последние результаты в теории спектров графов . Анналы дискретной математики. ISBN 0-444-70361-6 .
^ Сунада, Тошикадзу (2008), «Дискретный геометрический анализ», Труды симпозиумов по чистой математике , 77 : 51–86, doi : 10.1090/pspum/077/2459864 , ISBN 9780821844717 .
^ Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (март 2016 г.). «Вершинно-частотный анализ на графах». Прикладной и вычислительный гармонический анализ . 40 (2): 260–291. arXiv : 1307.5708 . дои : 10.1016/j.acha.2015.02.005 . ISSN 1063-5203 . S2CID 16487065 .
^ Станкович, Любиша; Дакович, Милош; Сейдич, Эрвин (июль 2017 г.). «Вершинно-частотный анализ: способ локализации спектральных компонентов графа [конспект лекций]». Журнал обработки сигналов IEEE . 34 (4): 176–182. Бибкод : 2017ISPM...34..176S . дои : 10.1109/msp.2017.2696572 . ISSN 1053-5888 . S2CID 19969572 .
^ Сакияма, Акиэ; Ватанабэ, Кана; Танака, Юичи (сентябрь 2016 г.). «Вейвлеты спектрального графа и банки фильтров с низкой ошибкой аппроксимации». Транзакции IEEE по обработке сигналов и информации в сетях . 2 (3): 230–245. дои : 10.1109/ципн.2016.2581303 . ISSN 2373-776X . S2CID 2052898 .
^ Бехжат, Хамид; Рихтер, Ульрике; Ван Де Виль, Дмитрий; Сорнмо, Лейф (15 ноября 2016 г.). «Жесткие рамки на графиках, адаптированные к сигналу» . Транзакции IEEE по обработке сигналов . 64 (22): 6017–6029. Бибкод : 2016ITSP...64.6017B . дои : 10.1109/tsp.2016.2591513 . ISSN 1053-587X . S2CID 12844791 .

Алон; Спенсер (2011), Вероятностный метод , Уайли .
Брауэр, Андриес ; Хемерс, Виллем Х. (2011), Спектры графов (PDF) , Springer
Хори; Линиал; Вигдерсон (2006), Экспандерные графики и их приложения (PDF)
Чанг, Фан (1997). Американское математическое общество (ред.). Спектральная теория графов . Провиденс, Род-Айленд, ISBN 0821803158 . MR 1421568 [первые 4 главы доступны на сайте] {{cite book}}: CS1 maint: постскриптум ( ссылка )
Швенк, Эй Джей (1973). «Почти все деревья коспектральны». В Харари, Фрэнк (ред.). Новые направления в теории графов . Нью-Йорк: Академическая пресса . ISBN 012324255X . ОСЛК 890297242 .
Богдан, Ника (2018). «Краткое введение в теорию спектральных графов» . Цюрих: EMS Press. ISBN 978-3-03719-188-0 .

Внешние ссылки

Спилман, Дэниел (2011). «Теория спектральных графов» (PDF) . [глава из Комбинаторных научных вычислений]
Спилман, Дэниел (2007). «Теория спектральных графов и ее приложения» . [представлено на конференции FOCS 2007]
Спилман, Дэниел (2004). «Теория спектральных графов и ее приложения» . [страница курса и конспекты лекций]

[1] Коллатц, Л. и Синоговиц, У. «Спектры конечного числа». Деф. Гамбург 21, 63–77, 1957.

[2] Вайсштейн, Эрик В. «Коспектральные графики» . Математический мир .

[3] Хосоя, Харуо ; Нагашима, Умпей; Хьюгадзи, Сатико (1994), «Топологические графы-близнецы. Наименьшая пара изоспектральных многогранных графов с восемью вершинами», Journal of Chemical Information and Modeling , 34 (2): 428–431, doi : 10.1021/ci00018a033 .

[FOOTNOTESchwenk1973275–307-4] Швенк (1973) , стр. 275–307.

[5] Годсил, Крис (7 ноября 2007 г.). «Почти все ли графы коспектральны?» (PDF) .

[6] Сунада, Тошикадзу (1985), "Римановы накрытия и изоспектральные многообразия", Ann. математики. , 121 (1): 169–186, номер документа : 10.2307/1971195 , JSTOR 1971195 .

[7] Брауэр и Хэмерс, 2011 г.

[8] Определение 2.1 в Hoory, Linial & Wigderson (2006).

[9] Дж. Додзюк, Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий, Trans. амер. Математика. Соц. 284 (1984), вып. 2, 787–794.

[FOOTNOTEAlonSpencer2011-10] Алон и Спенсер 2011 .

[11] Теорема 2.4 в книге Хори, Линиала и Вигдерсона (2006).

[chung-12] Jump up to: ^а ^б ^с Чанг, Фан (1997). Американское математическое общество (ред.). Спектральная теория графов . Провиденс, Род-Айленд, ISBN 0821803158 . MR 1421568 [первые 4 главы доступны на сайте] {{cite book}}: CS1 maint: постскриптум ( ссылка )

[13] Годсил, Крис (май 2009 г.). «Теоремы Эрдеша-Ко-Радо» (PDF) .

[14] Годсил, CD; Мигер, Карен (2016). Теоремы Эрдеша-Ко-Радо: алгебраические подходы . Кембридж, Великобритания. ISBN 9781107128446 . OCLC 935456305 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[cvet2-15] Jump up to: ^а ^б Собственные пространства графов , Драгош Цветкович , Питер Роулинсон, Слободан Симич (1997) ISBN 0-521-57352-1

[16] Драгош М. Цветкович, Майкл Дуб, Хорст Сакс , Спектры графов (1980)

[17] Цветкович, Драгош М.; Дуб, Майкл; Гутман Иван; Торгасев, А. (1988). Последние результаты в теории спектров графов . Анналы дискретной математики. ISBN 0-444-70361-6 .

[18] Сунада, Тошикадзу (2008), «Дискретный геометрический анализ», Труды симпозиумов по чистой математике , 77 : 51–86, doi : 10.1090/pspum/077/2459864 , ISBN 9780821844717 .

[19] Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (март 2016 г.). «Вершинно-частотный анализ на графах». Прикладной и вычислительный гармонический анализ . 40 (2): 260–291. arXiv : 1307.5708 . дои : 10.1016/j.acha.2015.02.005 . ISSN 1063-5203 . S2CID 16487065 .

[20] Станкович, Любиша; Дакович, Милош; Сейдич, Эрвин (июль 2017 г.). «Вершинно-частотный анализ: способ локализации спектральных компонентов графа [конспект лекций]». Журнал обработки сигналов IEEE . 34 (4): 176–182. Бибкод : 2017ISPM...34..176S . дои : 10.1109/msp.2017.2696572 . ISSN 1053-5888 . S2CID 19969572 .

[21] Сакияма, Акиэ; Ватанабэ, Кана; Танака, Юичи (сентябрь 2016 г.). «Вейвлеты спектрального графа и банки фильтров с низкой ошибкой аппроксимации». Транзакции IEEE по обработке сигналов и информации в сетях . 2 (3): 230–245. дои : 10.1109/ципн.2016.2581303 . ISSN 2373-776X . S2CID 2052898 .

[22] Бехжат, Хамид; Рихтер, Ульрике; Ван Де Виль, Дмитрий; Сорнмо, Лейф (15 ноября 2016 г.). «Жесткие рамки на графиках, адаптированные к сигналу» . Транзакции IEEE по обработке сигналов . 64 (22): 6017–6029. Бибкод : 2016ITSP...64.6017B . дои : 10.1109/tsp.2016.2591513 . ISSN 1053-587X . S2CID 12844791 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]