Перегляд вихідного коду сторінки Алгебрична теорія графів

[[Файл:Petersen1_tiny.svg|міні|270x270пкс|Високосиметричний [[граф Петерсена]], який є [[Вершинно-транзитивний граф|вершинно-транзитивним]], [[Симетричний граф|симетричним]], [[Дистанційно-транзитивний граф|дистанційно-транзитивним]] і [[Дистанційно-регулярний граф|дистанційно-регулярним]]. [[Відстань_(теорія_графів)#Пов'язані_поняття|Діаметр графа]] дорівнює 2. [[Автоморфізм графів|Група автоморфізмів]] графа містить 120 елементів і, фактично, є [[Симетрична група|симетричною групою]] <math>S_5</math>.]]
'''Алгебрична теорія графів'''&nbsp;— напрямок у [[Теорія графів|теорії графів]], що застосовує [[Алгебра|алгебричні]] методи до теоретико-графових задач (на додачу до {{Не перекладено|Геометрична теорія графів|геометричного|en|geometric graph theory}}, [[Комбінаторика|комбінаторного]] та [[Теорія графів|алгоритмічного]] напрямків). У свою чергу, алгебрична теорія графів поділяється на три гілки: [[Лінійна алгебра|лінійно-алгебричну]]{{Перехід|#Лінійна алгебра}}, [[Теорія груп|теоретико-групову]]{{Перехід|#Теорія груп}} і вивчає [[Інваріант графа|інваріанти графів]]{{Перехід|#Інваріанти графів}}.
[[Файл:TruncatedTetrahedron.gif|міні|270x270пкс|[[Граф Келі]] для [[Знакозмінна група|знакозмінної групи]] ''A''<sub>4</sub>, утворює [[зрізаний тетраедр]] у тривимірному просторі. Всі графи Келі [[Вершинно-транзитивний граф|вершинно-транзитивні]], але деякі вершинно-транзитивні графи (наприклад, [[граф Петерсена]]) не є графами Келі.]]

== Лінійна алгебра ==
{{Докладніше|Лінійна алгебра}}
Характерний представник лінійно-алгебричної гілки&nbsp;— [[спектральна теорія графів]], у якій вивчають [[Власний розклад матриці|спектри]] [[Матриця суміжності|матриці суміжності]] або [[Матриця Кірхгофа|матриці Кірхгофа]] графа. Для [[Граф Петерсена|графа Петерсена]], наприклад, спектр матриці суміжності дорівнює (-2, -2, -2, -2, 1, 1, 1, 1, 1, 3). Деякі теореми пов'язують властивості спектра з іншими [[Інваріант графа|інваріантами графа]]. Простий приклад: [[Зв'язний граф|зв'язний]] граф з [[Відстань (теорія графів)|діаметром]] <math>D</math> матиме щонайменше <math>D+1</math> різних значень у своєму спектрі{{Sfn|Biggs|1993}}. [[Алгебрична зв'язність|Властивості]] спектра графа використовують для аналізу [[Синхронізація|синхронізованості]] [[Теорія мереж|мереж]].
[[Файл:Petersen_graph_3-coloring.svg|міні|270x270пкс|Правильне розфарбування вершин [[Граф Петерсена|графа Петерсена]] трьома кольорами, мінімально можливим числом кольорів. З [[Хроматичний многочлен|хроматичного многочлена]] випливає, що існує 120 таких розмальовок у 3 кольори.]]

== Теорія груп ==
{{Докладніше|Теорія груп}}
У [[Теорія груп|теорико-груповій]] гілці використовують методи [[Абстрактна алгебра|загальної алгебри]] та [[Алгебрична комбінаторика|алгебричної комбінаторики]], а також [[геометрична теорія груп|геометричну теорію груп]]; одна з основних досліджуваних конструкцій&nbsp;— [[Автоморфізм графів|автоморфізми графів]] (утворюють [[Автоморфізм|групу]]). Увага приділяється різним сімействам графів, заснованих на [[Симетрія|симетрії]] (такі як [[Симетричний граф|симетричні графи]], [[Вершинно-транзитивний граф|вершинно-транзитивні графи]], [[Реберно-транзитивний граф|реберно-транзитивні графи]], [[Дистанційно-транзитивний граф|дистанційно-транзитивні графи]], [[Дистанційно-регулярний граф|дистанційно-регулярні графи]] і [[Сильно регулярний граф|сильно регулярні графи]]), та зв'язків між цими сімействами. Деякі з цих категорій містять мале число графів, так що їх можна [[Симетричний граф|перерахувати]]. За [[Теорема Фрухта|теоремою Фрухта]] всі [[Група (математика)|групи]] можна подати як групи автоморфізмів зв'язних графів (більше того, [[Кубічний граф|кубічних графів]]){{Sfn|Frucht|1949}}. Інший зв'язок з теорією груп&nbsp;— якщо задано будь-яку групу, можна утворити графи, відомі як [[Граф Келі|графи Келі]], і вони мають властивості, пов'язані зі структурою графа{{Sfn|Biggs|1993}}.

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

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

: <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>{{Sfn|Biggs|1993}},

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

== Див. також ==
* [[Алгебрична зв'язність]]

== Примітки ==
{{Reflist}}

== Література ==

* {{Стаття|author=[[Роберт Фрухт|R. Frucht]]|ref=Frucht|title=Graphs of Degree 3 with given abstract group|видання=Canad. J. Math.|issue=3|date=1949}}
* {{Книга
|автор = Norman Biggs
|ref = Biggs
|заголовок = Algebraic Graph Theory
|видання = 2nd
|місце = Cambridge
|видавництво = Cambridge University Press
|рік = 1993
|ISBN = 0-521-45897-8
}}
* {{Книга
|автор = L Babai
|ref = Babai
|відповідальний = R Graham, M Grötschel, L Lovász
|заголовок = Handbook of Combinatorics
|посилання = https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps
|рік = 1996
|видавництво = Elsevier
}}
* {{Книга
|автор = Chris Godsil, Gordon Royle
|ref = Chris Godsil, Gordon Royle
|заголовок = Algebraic Graph Theory
|серія = Graduate Texts in Mathematics
|том = 207
|видавництво = Springer-Verlag
|місце = New York
|рік = 2001
}}
{{Розділи математики}}
[[Категорія:Алгебраїчна теорія графів]]