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

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

Високосиметричний граф Петерсена, який є вершинно-транзитивним, симетричним, дистанційно-транзитивним і дистанційно-регулярним. (Діаметр графа) дорівнює 2. Група автоморфізмів графа містить 120 елементів і, фактично, є симетричною групою ${\displaystyle S_{5}}$.

Граф Келі для знакозмінної групи A₄, утворює зрізаний тетраедр у тривимірному просторі. Всі графи Келі вершинно-транзитивні, але деякі вершинно-транзитивні графи (наприклад, граф Петерсена) не є графами Келі.

Лінійна алгебра

Докладніше: Лінійна алгебра

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

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

Теорія груп

Докладніше: Теорія груп

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

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

Інваріанти графів

Докладніше: Інваріант графа

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

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

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

Див. також

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

Примітки

1. Biggs, 1993.
2. Frucht, 1949.
3. Babai, 1996.

Література

• . Graphs of Degree 3 with given abstract group // Canad. J. Math.. — 1949. — Вип. 3 (7 липня).
• Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge : Cambridge University Press, 1993. — .
• 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)