89
правок
Изменения
Нет описания правки
{{Лемма
|id = lem1
|statement= <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \geq </tex>, где <tex>\Delta (G)</tex>{{---}} максимальная степень вершины в графе
|proof= Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно <tex>\Delta(G)</tex> рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.
}}
Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее <tex>\chi '(G)</tex>. А именно что, <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \leqslant \Delta (G) + 1</tex>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
В данной же статье мы оценим [[Рёберная покраска двудольного графа#chromativ_index | хроматический индекс]] двудольных графов и предъявим алгоритм их раскраски.
== Рёберная раскраска двудольного графа ==
{{Лемма
|id = lem2
|statement= В [Основные определения теории графов#defBiparateGraph | [двудольном ]] <tex>k-</tex>-[[Основные определения теории графов#defRegularGraph | регулярном ]] с одинаковыми по размеру долями графе существует совершенное паросочетание.
|proof=
# Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходит''' <tex>k</tex>.
3) Мы получили регулярный двудольный граф с равными доля. По [[Рёберная раскраска двудольного графа#lem2 | нашей лемме]] в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]] и удалим его их графа.
4) Заметим что граф всё остался регулярным, так как степень каждой вершины уменьшилась на 1. Будем повторять процесс, пока в графе есть рёбра.
5) По итогу мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний. Так как на каждой итерации максимальная степень в графе уменьшалась на 1.
6) В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе
Таким образом мы нашли раскраску двудольного графа в <tex>\Delta(G)</tex> цветов и предъявили алгоритм её получения. А по [[Рёберная раскраска двудольного графа#lem1|лемме]] о нижней оценки, меньше цветов использовать нельзя. Следовательно <tex>\chi '(G) = \Delta(G)</tex>
Заметим, что наш жадный алгоритм может проводить кратные рёбра в графе. Однако ни [[Рёберная раскраска двудольного графа#lem2 | наша лемма]]о совершенном паросочетании, ни [[Теорема Холла | Теорема Холла]] не используют в своём доказательстве отсутствие таковых.
}}
