Алгебрична теорія графів

Алгебрична теорія графів — напрямок у теорії графів, що застосовує алгебричні методи до теоретико-графових задач (на додачу до геометричного^[en], комбінаторного та алгоритмічного напрямків). У свою чергу, алгебрична теорія графів поділяється на три гілки: лінійно-алгебричну^[⇨], теоретико-групову^[⇨] і вивчає інваріанти графів^[⇨].

Характерний представник лінійно-алгебричної гілки — спектральна теорія графів, у якій вивчають спектри матриці суміжності або матриці Кірхгофа графа. Для графа Петерсена, наприклад, спектр матриці суміжності дорівнює (-2, -2, -2, -2, 1, 1, 1, 1, 1, 3). Деякі теореми пов'язують властивості спектра з іншими інваріантами графа. Простий приклад: зв'язний граф з діаметром ${\displaystyle D}$ матиме щонайменше ${\displaystyle D+1}$ різних значень у своєму спектрі^[1]. Властивості спектра графа використовують для аналізу синхронізованості мереж.

У теорико-груповій гілці використовують методи загальної алгебри та алгебричної комбінаторики, а також геометричну теорію груп; одна з основних досліджуваних конструкцій — автоморфізми графів (утворюють групу). Увага приділяється різним сімействам графів, заснованих на симетрії (такі як симетричні графи, вершинно-транзитивні графи, реберно-транзитивні графи, дистанційно-транзитивні графи, дистанційно-регулярні графи і сильно регулярні графи), та зв'язків між цими сімействами. Деякі з цих категорій містять мале число графів, так що їх можна перерахувати. За теоремою Фрухта всі групи можна подати як групи автоморфізмів зв'язних графів (більше того, кубічних графів)^[2]. Інший зв'язок з теорією груп — якщо задано будь-яку групу, можна утворити графи, відомі як графи Келі, і вони мають властивості, пов'язані зі структурою графа^[1].

Групова гілка тісно пов'язана з лінійно-алгебричною, оскільки властивості симетрії графа відбиваються в його спектрі. Зокрема, спектр графа з високою симетрією, такого як граф Петерсена, має мало різних власних значень^[1] (у графа Петерсена 3 значення, що є найменшим можливим числом для графа з таким діаметром, як у графа Петерсена). Для графів Келі спектр може бути пов'язаний прямо зі структурою групи, зокрема, з її незвідними представленнями^[1][3].

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

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

зокрема, це означає, що граф Петерсена можна розфарбувати правильно одним або двома кольорами, але трьома кольорами його можна розфарбувати 120 різними способами. Багато робіт у цій галузі пов'язано зі спробами довести теорему про чотири фарби. Залишається багато відкритих питань, пов'язаних з інваріантами, наприклад, таких, як визначення графів, що мають той самий хроматичний многочлен, і визначення, які многочлени є хроматичними.

• Алгебрична зв'язність

• R. Frucht. Graphs of Degree 3 with given abstract group // Canad. J. Math.. — 1949. — Вип. 3 (5 листопада).
• 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)