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

Высокосимметричный граф Петерсена, который является вершинно-транзитивным, симметричным, дистанционно-транзитивным и дистанционно-регулярным. Диаметр графа равен 2. Группа автоморфизмов графа содержит 120 элементов и, фактически, является симметрической группой $S_{5}$.

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

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

Линейная алгебра

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

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

Теория групп

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

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

Инварианты графов

Алгебраические свойства инвариантов графов, таких, как хроматические многочлены, многочлены Татта, инварианты узлов, позволяют изучать структуру графов алгебраическими средствами. Например, хроматический многочлен графа, подсчитывает число его правильных раскрасок вершин; для графа Петерсена этот многочлен равен:

$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$,

в частности, это означает, что граф Петерсена нельзя раскрасить правильно одним или двумя цветами, но тремя цветами его можно раскрасить 120 различными способами. Много работ в этой области связано с попытками доказать теорему о четырёх красках. Остаётся много открытых вопросов, связанных с инвариантами, например, таких, как определение графов, имеющих тот же самый хроматический многочлен, и определение, какие многочлены являются хроматическими.

См. также

• Перечисление графов
• Спектральная теория графов
• Топологическая теория графов

Литература

• R. Frucht. Graphs of Degree 3 with given abstract group // Canad. J. Math.. — 1949. — Вып. 3.
• Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — ISBN 0-521-45897-8.
• L Babai. Handbook of Combinatorics / R Graham, M Grötschel, L Lovász. — Elsevier, 1996.
• Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics).