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

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

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

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

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

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

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

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

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

графа инвариантов Изучение

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

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

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

↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Cambridge University Press, ISBN 0-521-45897-8 , Збл 0797.05032
^ Фрухт, Р. (1949), «Графы степени 3 с заданной абстрактной группой», Can. Дж. Математика. , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6
^ * Бабай, Л. (1996), «Группы автоморфизмов, изоморфизм, реконструкция» , в Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.), Справочник по комбинаторике , Elsevier, стр. 1447–1540, ISBN 0-444-82351-4 , Zbl 0846.05042 , заархивировано из оригинала 11 июня 2010 г. , получено 27 марта 2009 г.

Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов , Тексты для выпускников по математике, том. 207, Спрингер, ISBN 0-387-95220-9 , Збл 0968.05002 .

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

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

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

[2] Фрухт, Р. (1949), «Графы степени 3 с заданной абстрактной группой», Can. Дж. Математика. , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6

[babai-3] * Бабай, Л. (1996), «Группы автоморфизмов, изоморфизм, реконструкция» , в Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.), Справочник по комбинаторике , Elsevier, стр. 1447–1540, ISBN 0-444-82351-4 , Zbl 0846.05042 , заархивировано из оригинала 11 июня 2010 г. , получено 27 марта 2009 г.

[1]

[2]

[3]

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