Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск кососпектральных графиков [ править ]

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

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

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

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

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

Неравенство Чигера [ править ]

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

Константа Чигера [ править ]

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

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

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

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

Неравенство Чигера [ править ]

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

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

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

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

Предположим, что это -регулярный граф на вершинах с наименьшим собственным значением . Потом:

где обозначает его число независимости .

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

Исторический очерк [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Коллатца, Л. и Sinogowitz, У. "Spektren endlicher Графен." Abh. Математика. Сем. Univ. Гамбург, 21, 63–77, 1957.
  2. ^ Weisstein, Eric W. "коспектральные графы" . MathWorld .
  3. ^ Хосоя, Харуо ; Нагасима, Умпей; Hyugaji, Сатико (1994), "Топологические спаренные графики Наименьший пара изоспектральных многогранных графов с восемью вершинами.", Журнал химической информации и моделирования , 34 (2): 428-431, DOI : 10.1021 / ci00018a033.
  4. ^ Schwenk (1973) , стр. 275-307.
  5. ^ Godsil, Крис (7 ноября 2007). "Практически все графики коспектральны?" (PDF) .
  6. ^ Сунада, Тошиказу (1985), "Римановы накрытия и изоспектральные многообразия", Ann. математики. , 121 (1): 169-186, DOI : 10,2307 / 1971195 , JSTOR 1971195 .
  7. ^ См. ( Brouwer & Haemers 2011 ) во внешних ссылках .
  8. ^ Определение 2.1 в Hoory, Linial & Widgerson (2006)
  9. ^ Дж. Додзюк, Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий, Тр. Амер. Математика. Soc. 284 (1984), нет. 2, 787-794.
  10. Перейти ↑ Alon & Spencer, 2011 .
  11. ^ Теорема 2.4 в Hoory, Linial & Widgerson (2006)
  12. ^ Godsil, Крис (май 2009). "Теоремы Эрдеша-Ко-Радо" (PDF) .
  13. ^ 1949-, Годсил, CD (Кристофер Дэвид) (2016). Теоремы Эрдеша-Ко-Радо: алгебраические подходы . Мигер, Карен (учитель колледжа). Кембридж, Соединенное Королевство. ISBN 9781107128446. OCLC  935456305 .CS1 maint: числовые имена: список авторов ( ссылка )
  14. ^ a b Собственные подпространства графов , Драгош Цветкович , Питер Роулинсон, Слободан Симич (1997) ISBN 0-521-57352-1 
  15. ^ Драгош М. Цветкович, Майкл Дуб, Хорст Сакс , Спектры графов (1980)
  16. ^ Cvetković, Dragoš M .; Дуб, Майкл; Гутман, Иван; Торгасев, А. (1988). Последние результаты в теории графовых спектров . Анналы дискретной математики. ISBN 0-444-70361-6.
  17. ^ Сунада, Тошиказ (2008), "Дискретный геометрический анализ", Труды симпозиумов в чистых математиках , 77 : 51-86, DOI : 10,1090 / pspum / 077/2459864 , ISBN 9780821844717.
  18. ^ Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (март 2016 г.). «Вершинно-частотный анализ на графах». Прикладной и вычислительный гармонический анализ . 40 (2): 260–291. arXiv : 1307,5708 . DOI : 10.1016 / j.acha.2015.02.005 . ISSN 1063-5203 . 
  19. ↑ Станкович, Любиса; Дакович, Милош; Сейдич, Эрвин (июль 2017 г.). «Вершинно-частотный анализ: способ локализации спектральных составляющих графа [Конспект лекции]». Журнал обработки сигналов IEEE . 34 (4): 176–182. Bibcode : 2017ISPM ... 34..176S . DOI : 10.1109 / msp.2017.2696572 . ISSN 1053-5888 . 
  20. ^ Сакияма, Акиэ; Ватанабэ, Кана; Танака, Юичи (сентябрь 2016 г.). «Спектральные вейвлеты и банки фильтров с низкой ошибкой аппроксимации». IEEE Transactions по обработке сигналов и информации по сетям . 2 (3): 230–245. DOI : 10.1109 / tsipn.2016.2581303 . ISSN 2373-776X . 
  21. ^ Бехджат, Хамид; Рихтер, Ульрике; Ван де Виль, Дмитрий; Сорнмо, Лейф (15 ноября 2016 г.). «Узкие рамки, адаптированные к сигналу на графиках» . Транзакции IEEE по обработке сигналов . 64 (22): 6017–6029. Bibcode : 2016ITSP ... 64.6017B . DOI : 10.1109 / tsp.2016.2591513 . ISSN 1053-587X . 
  • Швенк, AJ (1973). «Почти все деревья - коспектральные». В Харари, Фрэнк (ред.). Новые направления в теории графов . Нью-Йорк: Academic Press . ISBN 012324255X. OCLC  890297242 .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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