Введение

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

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

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

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

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

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

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