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

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

Високосиметричний граф Петерсена, який є вершинно-транзитивним, симетричним, дистанційно-транзитивним і дистанційно-регулярним. Діаметр графа дорівнює 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 (25 листопада).
• 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)