Степень вершины (теория графов)
- 1 year ago
- 0
- 0
Спектральная теория графов — направление в теории графов , изучающее свойства графов , характеристических многочленов , собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа .
Неориентированный граф имеет симметричную матрицу смежности, а потому имеет вещественные собственные значения ( мультимножество которых называется спектр графа ) и полное множество собственных векторов .
В то время как матрица смежности графа зависит от нумерации вершин, его спектр является инвариантом графа .
Спектральная теория графов занимается также параметрами, которые определяются путём умножения собственных значений матриц, связанных с графом, таких, как число Колен де Вердьера .
Два графа называются или коспектральными, если матрицы смежности графов имеют одинаковые мультимножества собственных значений.
Изоспектральные графы не обязательно изоморфны , но изоморфные графы всегда изоспектральны. Минимальная пара неизоморфных коспектральных неориентированных графов — , то есть звезда с пятью вершинами и объединение цикла с 4 вершинами и графа, состоящего из единственной вершины, что показали Коллац и Сингович в 1957 году. Наименьшая пара неизоморфных коспектральных полиэдральных графов — два эннеаэдра с восемью вершинами в каждом .
Почти все деревья имеют коспектральные им графы, то есть доля деревьев порядка , для каждого из которых существует коспектральный граф, стремится к 1 при росте .
Изоспектральные графы конструируются при помощи .
Знаменитое неравенство Чигера из римановой геометрии имеет дискретный аналог, использующий матрицу Кирхгофа. Возможно, это наиболее важная теорема в спектральной теории графов и один из самых полезных фактов в алгоритмических приложениях. Неравенство оценивает наименьший разрез графа посредством второго собственного значения матрицы Кирхгофа.
Константа Чигера (или число Чигера , или изопериметрическое число ) графа — это числовая мера того, что граф имеет «узкое горло». Константа Чигера как мера наличия «узкого горла» представляет большой интерес во многих областях. Например, при построении сильно связанных компьютерная сетей , тасовании карт и (в частности, при изучении гиперболических 3- многообразий ).
Формально, константа Чигера графа с вершинами определяется как
где минимум берётся по всем непустым множествам максимум с вершинами и — рёберная граница множества , то есть множество рёбер, имеющих в точности одну конечную вершину в .
Если граф является -регулярным, существует связь между и спектральным промежутком графа . Неравенство Чигера исследовали Таннер, Алон и Мильман . Неравенство утверждает, что
Это неравенство тесно связано с * для цепей Маркова и его можно рассматривать как дискретную версию неравентства Чигера в римановой геометрии .
Спектральная теория графов возникла в 1950—1960 годах. Монография 1980 года « Спектры графов » ( Spectra of Graphs ) Цветковича, Дооба и Сакса (Cvetković, Michael Doob, Sachs) обобщила почти все исследования в этой области, известные к тому моменту. В 1988 году вышло обновлённое обозрение « Последние исследования в теории спектра графа » . Третье издание книги « Спектры графов » (1995) содержит итоги дальнейших вкладов в этой области .
Кроме теоретических исследований о связи структурных и спектральных свойств графов, другим источником стали исследования в квантовой химии , но связь этих двух направлений выяснена много позже .