WikiSort.ru - Не сортированное

Использующие линейную алгебру

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

Использующие теорию групп

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

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

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

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