Алгебрична теорія графів — Вікіпедія

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

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

Лінійна алгебра[ред. | ред. код]

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

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

Теорія груп[ред. | ред. код]

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

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

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

Інваріанти графів[ред. | ред. код]

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

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

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 (21 квітня).
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)

[FOOTNOTEBiggs1993-1] а ^б ^в ^г ^д Biggs, 1993.

[FOOTNOTEFrucht1949-2] Frucht, 1949.

[FOOTNOTEBabai1996-3] Babai, 1996.

[1]

[2]

[3]