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

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

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

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

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

Изоспектральные графы

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

Изоспектральные графы не обязательно изоморфны , но изоморфные графы всегда изоспектральны. Минимальная пара неизоморфных коспектральных неориентированных графов — , то есть звезда с пятью вершинами и объединение цикла с 4 вершинами и графа, состоящего из единственной вершины, что показали Коллац и Сингович в 1957 году. Наименьшая пара неизоморфных коспектральных полиэдральных графов — два эннеаэдра с восемью вершинами в каждом .

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

Изоспектральные графы конструируются при помощи .

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

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

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

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

Формально, константа Чигера графа с вершинами определяется как

где минимум берётся по всем непустым множествам максимум с вершинами и рёберная граница множества , то есть множество рёбер, имеющих в точности одну конечную вершину в .

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

Если граф является -регулярным, существует связь между и спектральным промежутком графа . Неравенство Чигера исследовали Таннер, Алон и Мильман . Неравенство утверждает, что

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

История

Спектральная теория графов возникла в 1950—1960 годах. Монография 1980 года « Спектры графов » ( Spectra of Graphs ) Цветковича, Дооба и Сакса (Cvetković, Michael Doob, Sachs) обобщила почти все исследования в этой области, известные к тому моменту. В 1988 году вышло обновлённое обозрение « Последние исследования в теории спектра графа » . Третье издание книги « Спектры графов » (1995) содержит итоги дальнейших вкладов в этой области .

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

См. также

Примечания

  1. Collatz, L. and Sinogowitz, U. Spektren endlicher Grafen // Abh. Math. Sem. Univ. Hamburg. — 1957. — № 21 . — С. 63–77 .
  2. Weisstein, Eric W. (англ.) на сайте 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 : .
  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 .
  6. , Определение 2.1.
  7. .
  8. , Теорема 2.4.
  9. Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectra of Graphs. — 1980.
  10. Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev. . — 1988. — (Annals of Discrete mathematics). — ISBN 0-444-70361-6 . 5 ноября 2017 года.
  11. Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. . — 1997. — ISBN 0-521-57352-1 .

Литература

  • Shlomo Hoory, Nathan Linial and Avi Wigderson. // 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. . — American Mathematical Society, 1992. — Т. 92. — 207 с. — (Cbms Regional Conference Series in Mathematics). — ISBN 978-0821803158 .

Ссылки

  • Dan Spielman. (2004).
  • Daniel Spielman. . — presented at FOCS 2007 Conference.
  • Lu, Lincoln (2009). Дата обращения: 23 ноября 2014. Архивировано из 5 марта 2012 года.
Источник —

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