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

напрямок у теорії графів

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

Високосиметричний граф Петерсена, який є вершинно-транзитивним, симетричним, дистанційно-транзитивним і дистанційно-регулярним. Діаметр графа дорівнює 2. Група автоморфізмів графа містить 120 елементів і, фактично, є симетричною групою .
Граф Келі для знакозмінної групи A4, утворює зрізаний тетраедр у тривимірному просторі. Всі графи Келі вершинно-транзитивні, але деякі вершинно-транзитивні графи (наприклад, граф Петерсена) не є графами Келі.

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

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

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

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

Теорія груп ред.

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

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

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

Інваріанти графів ред.

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

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

 [1],

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

Див. також ред.

Примітки ред.

Література ред.

  • R. Frucht. Graphs of Degree 3 with given abstract group // Canad. J. Math.. — 1949. — Вип. 3 (2 квітня).
  • 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)