11.11.2020

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Формально, константа Чигера h ( G ) {displaystyle h(G)} графа G {displaystyle G} с n {displaystyle n} вершинами определяется как

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

где минимум берётся по всем непустым множествам S {displaystyle S} максимум с n / 2 {displaystyle n/2} вершинами и ∂ ( S ) {displaystyle partial (S)} — рёберная граница множества S {displaystyle S} , то есть множество рёбер, имеющих в точности одну конечную вершину в S {displaystyle S} .

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

Если граф G {displaystyle G} является d {displaystyle d} -регулярным, существует связь между h ( G ) {displaystyle h(G)} и спектральным промежутком d − λ 2 {displaystyle d-lambda _{2}} графа G {displaystyle G} . Неравенство Чигера исследовали Таннер, Алон и Мильман. Неравенство утверждает, что

1 2 ( d − λ 2 ) ≤ h ( G ) ≤ 2 d ( d − λ 2 ) . {displaystyle { frac {1}{2}}(d-lambda _{2})leq h(G)leq {sqrt {2d(d-lambda _{2})}}.}

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

История

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

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


Похожие новости:

Дом Липпе

Дом Липпе
Липпе (нем. Lippe) — вестфальский владетельный дом, до XX века правивший графствами (княжествами) Липпе-Детмольд и Шаумбург-Липпе. Фамилия и регион Липпе получили название от одноименной реки. Под

Жеро д’Арманьяк (виконт Фезансаге)

Жеро д’Арманьяк (виконт Фезансаге)
Жеро д’Арманьяк (ум. 1403) — виконт Фезанзаге (1390—1402), граф Пардиака. Сын Жана (ум. 1390), виконта Фезанзаге и Брюлуа, и его жены Маргариты де Кармен. Троюродный брат графов д’Арманьяк Жана III и

Решётка (теория графов)

Решётка (теория графов)
Граф решётки — это граф, рисунок которого, вложенный в некоторое евклидово пространство Rn, образует регулярную мозаику. Это подразумевает, что группа биективных преобразований, переводящая граф в

Теория случайных матриц

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

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Недорогие печи Лиговъ - качественная российская продукция
Недорогие печи Лиговъ - качественная российская продукция
Оснащенные «подовым горением» печи-камины стала выпускать компания «Лиговъ». От «колосниковых»...
Камины Астов (Astov) - российская продукция премиум-класса
Камины Астов (Astov) - российская продукция премиум-класса
Камины устанавливаются в загородных домах и квартирах все чаще. Ассоциации они вызывают обычно...
Что стоит принять во внимание прежде, чем вступить в СРО строителей
Что стоит принять во внимание прежде, чем вступить в СРО строителей
Вступление в СРО строителей в наше время – дело необходимое. Членство поможет повысить качество...
Виды окон ПВХ и их преимущества
Виды окон ПВХ и их преимущества
В конце девяностых годов прошлого века в нашей стране появились пластиковые окна. Они сразу же...
Особенности проведения отделки балкона
Особенности проведения отделки балкона
Балкон — это особое пространство квартиры, которое отличается небольшими квадратными метрами и...
Что такое предпроектная документация и для чего она нужна
Что такое предпроектная документация и для чего она нужна
Прединвестиционная стадия характеризуется возможностью создания конечного результата. Это не...
Особенности мобильных офисных перегородок. Основы правильной организации рабочего пространства
Особенности мобильных офисных перегородок. Основы правильной организации рабочего пространства
Мобильные офисные перегородки — это современные решения, помогающие быстро и эффективно зонировать...
Все новости