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

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

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

Теория групп

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

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

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

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

${\displaystyle 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. / 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).