Алгебраическая теория графов

В высшей степени симметричный граф, граф Петерсена , который является вершинно-транзитивным , симметричным , дистанционно-транзитивным и дистанционно-регулярным . Она имеет диаметр 2. Ее группа автоморфизмов состоит из 120 элементов и фактически является симметрической группой .

{\ displaystyle S_ {5}}

Алгебраическая теория графов - это раздел математики, в котором алгебраические методы применяются к задачам о графах . Это контрастирует с геометрическим , комбинаторным или алгоритмическим подходами. Есть три основных раздела алгебраической теории графов, включающие использование линейной алгебры , использование теории групп и изучение инвариантов графов .

Разделы алгебраической теории графов [ править ]

Использование линейной алгебры [ править ]

Первая ветвь алгебраической теории графов включает изучение графов в связи с линейной алгеброй . В частности, она изучает спектр из матрицы смежности , или лапласиан матрицы графа (эта часть алгебраической теории графов также называется спектральной теорией графов ). Для графа Петерсена , например, спектр матрицы смежности равен (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Некоторые теоремы связывают свойства спектра с другими свойствами графа . В качестве простого примера, связный граф диаметра D будет иметь не менее D+1 различные значения в его спектре. ^[1] Аспекты графа спектров были использованы при анализе synchronizability из сетей .

Использование теории групп [ править ]

Семейства графов, определяемые их автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	строго регулярный
↓
симметричный (дуго-транзитивный)	←	t -транзитивный, t ≥ 2		кососимметричный
↓
_{(если связаны)} вершинно- и реберно-транзитивные	→	реберно-транзитивные и регулярные	→	реберно-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	_{(если двудольный)} бирегулярный
↑
Граф Кэли	←	нулевой симметричный		асимметричный

Вторая ветвь алгебраической теории графов включает изучение графов в связи с теорией групп , особенно группами автоморфизмов и геометрической теорией групп . Основное внимание уделяется различным семействам графов, основанных на симметрии (например, симметричные графы , вершинно-транзитивные графы , реберно-транзитивные графы , дистанционно-транзитивные графы , дистанционно-регулярные графы и строго регулярные графы ), а также взаимосвязи включения между эти семьи. Некоторые из таких категорий графов достаточно разрежены, чтобы можно было составить списки графов. КПо теореме Фрухта все группы могут быть представлены как группа автоморфизмов связного графа (действительно, кубического графа ). ^[2] Другая связь с теорией групп состоит в том, что для любой группы могут быть сгенерированы симметричные графы, известные как графы Кэли , и у них есть свойства, связанные со структурой группы. ^[1]

Граф Кэли для знакопеременной группы A ₄ , образуя усеченный тетраэдр в трех измерениях. Все графы Кэли транзитивны по вершинам , но некоторые графы с транзитивными вершинами (например, граф Петерсена ) не являются графами Кэли.

Правильная раскраска вершин графа Петерсена в 3 цвета, минимально возможное количество. По хроматическому полиному таких раскрасок по 3 цвета 120.

Эта вторая ветвь алгебраической теории графов связана с первой, поскольку свойства симметрии графа отражаются в его спектре. В частности, спектр высокосимметричного графа, такого как граф Петерсена, имеет несколько различных значений ^[1] (граф Петерсена имеет 3, что является минимально возможным с учетом его диаметра). Для графов Кэли спектр может быть напрямую связан со структурой группы, в частности с ее неприводимыми характерами . ^[1]^[3]

Изучение инвариантов графа [ править ]

Наконец, третья ветвь алгебраической теории графов касается алгебраических свойств инвариантов графов, особенно хроматического многочлена , многочлена Тутте и инвариантов узлов . Хроматический многочлен графа, например, подсчитывает количество его правильных раскрасок вершин . Для графа Петерсена этот многочлен равен . ^[1] В частности, это означает, что граф Петерсена не может быть правильно раскрашен в один или два цвета, но может быть раскрашен 120 различными способами в 3 цвета. Многие работы в этой области алгебраической теории графов были мотивированы попытками доказать теорему о четырех цветах . Однако есть еще много ${\ Displaystyle т (т-1) (т-2) (т ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775т-352)}$ открытые проблемы , такие как определение характеристик графов, которые имеют один и тот же хроматический полином, и определение того, какие полиномы являются хроматическими.

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

Теория спектральных графов
Алгебраическая комбинаторика
Алгебраическая связность
Разложение Дульмаджа – Мендельсона.
Свойство графа
Матрица смежности

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

^ a b c d e Биггс, Норман (1993), алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8
^ Р. Фрухт . Графы степени 3 с заданной абстрактной группой, Can. J. Math. 3 1949 г.
^ * Бабай, L (1996), "Группы автоморфизмов, изоморфизм, реконструкция" , в Graham, R; Grötschel, M ; Ловас, L (ред.), Справочник по комбинаторике , Elsevier

Годсил, Крис ; Ройл, Гордон (2001), алгебраическая теория графов , Graduate Texts in Mathematics, 207 , New York: Springer-Verlag.

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

СМИ, связанные с теорией алгебраических графов, на Викискладе?

[biggs-1] Биггс, Норман (1993), алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8

[2] Р. Фрухт . Графы степени 3 с заданной абстрактной группой, Can. J. Math. 3 1949 г.

[babai-3] * Бабай, L (1996), "Группы автоморфизмов, изоморфизм, реконструкция" , в Graham, R; Grötschel, M ; Ловас, L (ред.), Справочник по комбинаторике , Elsevier

[1]