Теория спектральных графов - Spectral graph theory

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

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

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

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

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

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

Два коспектральных эннеэдра, наименьший возможный кососпектральный многогранные графы

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

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

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

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

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

Коспектральные товарищи

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

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

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

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

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

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

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

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

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

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

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

Постоянная Чигера

Основная статья: Константа Чигера (теория графов)

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

Более формально постоянная Чигера час(грамм) графа грамм на п вершины определяется как

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

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

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

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

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

Это неравенство тесно связано с Чигер связан за Цепи Маркова и может рассматриваться как дискретная версия Неравенство Чигера в Риманова геометрия.

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

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

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

$${\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}$$

куда ${\displaystyle \alpha (G)}$ обозначает его число независимости.

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

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

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

Смотрите также

• Сильно регулярный граф
• Алгебраическая связность
• Алгебраическая теория графов
• Спектральная кластеризация
• Спектральный анализ формы
• Индекс эстрады
• Ловас тета
• График расширителя

Рекомендации

1. Коллатц, Л. и Синоговиц, У. "Spektren endlicher Grafen". Abh. Математика. Сем. Univ. Гамбург, 21, 63–77, 1957.
2. Вайсштейн, Эрик В. «Коспектральные графики». MathWorld.
3. Хосоя, Харуо; Нагасима, Умпей; Хюгаджи, Сатико (1994), "Топологические двойные графы. Наименьшая пара изоспектральных многогранных графов с восемью вершинами", Журнал химической информации и моделирования, 34 (2): 428–431, Дои:10.1021 / ci00018a033.
4. Швенк (1973) С. 275-307.
5. Годсил, Крис (7 ноября 2007 г.). "Практически все графики коспектральны?" (PDF).
6. Сунада, Тошиказу (1985), "Римановы накрытия и изоспектральные многообразия", Анна. математики., 121 (1): 169–186, Дои:10.2307/1971195, JSTOR  1971195.
7. Видеть (Брауэр и Хемерс 2011 ) в внешняя ссылка.
8. Определение 2.1 в Хори, Линиал и Виджерсон (2006) Ошибка harvtxt: нет цели: CITEREFHooryLinialWidgerson2006 (помощь)
9. Додзюк Ю. Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий // Тр. Амер. Математика. Soc. 284 (1984), нет. 2, 787-794.
10. Алон и Спенсер 2011. Ошибка sfn: нет цели: CITEREFAlonSpencer2011 (помощь)
11. Теорема 2.4 в Хори, Линиал и Виджерсон (2006) Ошибка harvtxt: нет цели: CITEREFHooryLinialWidgerson2006 (помощь)
12. Годсил, Крис (май 2009 г.). "Теоремы Эрдеша-Ко-Радо" (PDF).
13. 1949-, Годсил, К. Д. (Кристофер Дэвид) (2016). Теоремы Эрдеша-Ко-Радо: алгебраические подходы. Мигер, Карен (учитель колледжа). Кембридж, Соединенное Королевство. ISBN  9781107128446. OCLC  935456305.
14. Собственные подпространства графов, к Драгош Цветкович, Питер Роулинсон, Слободан Симич (1997) ISBN  0-521-57352-1
15. Драгош М. Цветкович, Майкл Дуб, Хорст Сакс, Спектры графиков (1980)
16. Цветкович, Драгош М .; Дуб, Майкл; Гутман, Иван; Торгасев, А. (1988). Последние результаты в теории графовых спектров.. Анналы дискретной математики. ISBN  0-444-70361-6.
17. Сунада, Тошиказу (2008), "Дискретный геометрический анализ", Труды симпозиумов по чистой математике, 77: 51–86, Дои:10.1090 / pspum / 077/2459864, ISBN  9780821844717.
18. Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (март 2016 г.). «Вершинно-частотный анализ на графах». Прикладной и вычислительный гармонический анализ. 40 (2): 260–291. arXiv:1307.5708. Дои:10.1016 / j.acha.2015.02.005. ISSN  1063-5203.
19. Станкович, Любиса; Дакович, Милош; Сейдич, Эрвин (июль 2017 г.). «Вершинно-частотный анализ: способ локализации спектральных компонент графа [Конспект лекции]». Журнал IEEE Signal Processing Magazine. 34 (4): 176–182. Bibcode:2017ISPM ... 34..176S. Дои:10.1109 / msp.2017.2696572. ISSN  1053-5888.
20. Сакияма, Акиэ; Ватанабэ, Кана; Танака, Юичи (сентябрь 2016 г.). «Спектральные вейвлеты и банки фильтров с низкой ошибкой аппроксимации». Транзакции IEEE при обработке сигналов и информации по сетям. 2 (3): 230–245. Дои:10.1109 / ципн.2016.2581303. ISSN  2373-776X.
21. Бехджат, Хамид; Рихтер, Ульрике; Ван де Виль, Дмитрий; Сорнмо, Лейф (15 ноября 2016 г.). "Узкие рамки, адаптированные к сигналу, на графиках". Транзакции IEEE при обработке сигналов. 64 (22): 6017–6029. Bibcode:2016ITSP ... 64.6017B. Дои:10.1109 / чайная ложка.2016.2591513. ISSN  1053-587X.

• Швенк, А. Дж. (1973). «Почти все деревья - коспектральные». В Харари, Фрэнк (ред.). Новые направления в теории графов. Нью-Йорк: Академическая пресса. ISBN  012324255X. OCLC  890297242.

дальнейшее чтение

• Чанг, Фань (1997). Американское математическое общество (ред.). Теория спектральных графов. Провиденс, Р.И. ISBN  0821803158. МИСТЕР  1421568 [первые 4 главы доступны на сайте]

внешняя ссылка

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