Loading AI tools
Из Википедии, свободной энциклопедии
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
Неориентированный граф имеет симметричную матрицу смежности, а потому имеет вещественные собственные значения (мультимножество которых называется спектр графа) и полное множество собственных векторов.
В то время как матрица смежности графа зависит от нумерации вершин, его спектр является инвариантом графа.
Спектральная теория графов занимается также параметрами, которые определяются путём умножения собственных значений матриц, связанных с графом, таких, как число Колен де Вердьера.
Два графа называются изоспектральными[англ.] или коспектральными, если матрицы смежности графов имеют одинаковые мультимножества собственных значений.
Изоспектральные графы не обязательно изоморфны, но изоморфные графы всегда изоспектральны. Минимальная пара неизоморфных коспектральных неориентированных графов — , то есть звезда с пятью вершинами и объединение цикла с 4 вершинами и графа, состоящего из единственной вершины, что показали Коллац и Сингович[1][2] в 1957 году. Наименьшая пара неизоморфных коспектральных полиэдральных графов — два эннеаэдра с восемью вершинами в каждом[3].
Почти все деревья имеют коспектральные им графы, то есть доля деревьев порядка , для каждого из которых существует коспектральный граф, стремится к 1 при росте [4].
Изоспектральные графы конструируются при помощи метода Сунада[англ.][5].
Знаменитое неравенство Чигера из римановой геометрии имеет дискретный аналог, использующий матрицу Кирхгофа. Возможно, это наиболее важная теорема в спектральной теории графов и один из самых полезных фактов в алгоритмических приложениях. Неравенство оценивает наименьший разрез графа посредством второго собственного значения матрицы Кирхгофа.
Константа Чигера (или число Чигера, или изопериметрическое число) графа — это числовая мера того, что граф имеет «узкое горло». Константа Чигера как мера наличия «узкого горла» представляет большой интерес во многих областях. Например, при построении сильно связанных компьютерная сетей, тасовании карт и топологии низких размерностей[англ.] (в частности, при изучении гиперболических 3-многообразий).
Формально, константа Чигера графа с вершинами определяется как
где минимум берётся по всем непустым множествам максимум с вершинами и — рёберная граница множества , то есть множество рёбер, имеющих в точности одну конечную вершину в [6].
Если граф является -регулярным, существует связь между и спектральным промежутком графа . Неравенство Чигера исследовали Таннер, Алон и Мильман[7]. Неравенство утверждает, что[8]
Это неравенство тесно связано с границей Чигера[англ.]* для цепей Маркова и его можно рассматривать как дискретную версию неравентства Чигера в римановой геометрии.
Спектральная теория графов возникла в 1950—1960 годах. Монография 1980 года «Спектры графов» (Spectra of Graphs)[9] Цветковича, Дооба и Сакса (Cvetković, Michael Doob, Sachs) обобщила почти все исследования в этой области, известные к тому моменту. В 1988 году вышло обновлённое обозрение «Последние исследования в теории спектра графа»[10]. Третье издание книги «Спектры графов» (1995) содержит итоги дальнейших вкладов в этой области[11].
Кроме теоретических исследований о связи структурных и спектральных свойств графов, другим источником стали исследования в квантовой химии, но связь этих двух направлений выяснена много позже[11].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.