89
правок
Изменения
Нет описания правки
{{Определение
|id = edge_colouring
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1}...\ldots c_{t}\}</tex> {{---}} ''множество красок'' такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> инцидентных одной вершине верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.
}}
}}
== Некоторое Некоторые оценки хроматического индекса ==
{{Лемма
|id = lem1
|statement= <tex>\forall\ G(V, E) : \chi '(G) \geq \Delta (G)</tex>
|proof= Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно <tex>\Delta(G)</tex> рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.
}}
Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее <tex>\chi '(G)</tex>. А именно что, <tex>\forall\ G(V, E) : \Delta (G) \leq leqslant \chi '(G) \leq leqslant \Delta (G) + 1</tex>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
В данной же статье мы оценим [[Рёберная покраска двудольного графа#chromativ_index | хроматический индекс]] двудольных графов и предъявим алгоритм их раскраски.
== Рёберная раскраска двудольного графа ==
{{Лемма
|id = lem2
|statement= В двудольном <tex>k-</tex>регулярном с одинаковыми по размеру долями графе существует совершенное паросочетание.
|proof=
# Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходит''' <tex>k</tex>.
# Посчитаем количество рёбер <tex>m_{L}</tex> в данном подграфе. В силу его двудольности это число будет равняться сумме степеней вершин одной из долей. <tex>m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k</tex>. Из этого мы получаем, что <tex>|L|\leqslant |R|</tex>.
# Значит в данном графе выполняется [[Теорема Холла | Теорема Холла]]. Из чего следует, что в нём есть совершенное паросочетание.
}}
{{Теорема
|statement= Существует рёберная раскраска двудольного графа <tex>G</tex> в <tex>\Delta(G)</tex> цветов. Иными слова для двудольного графа <tex>\chi '(G) = \Delta(G)</tex>
|proof=
1) Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством изолированных вершин
2) Следующим жадным алгоритмом сделаем его <tex>\Delta(G)-</tex>регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром
Докажем, что такой жадный алгоритм всегда выполняет поставленную задачу.
Предположим, что это не так, и, не нарушая общности, у нас остались вершины в правой доле степени меньше <tex>\Delta(G)</tex>, а в левой таких вершин нет. Давайте посчитаем количество рёбер <tex>m</tex> в графе. Из левой доли исходит <tex>|L| \cdot \Delta(G)</tex> рёбер. В правую же приходит не более <tex>|R| \cdot \Delta(G)</tex> рёбер, но так как существует вершина степени меньше <tex>\Delta(G)</tex>. То неравенство строгое. Получается <tex>|L| \cdot \Delta(G) = m < |R| \cdot \Delta(G)</tex>. Но в нашем графе <tex>|L| = |R|</tex>. Следовательно <tex>\Delta(G) < \Delta(G)</tex>, что приводит нас к противоречию
3) Мы получили регулярный двудольный граф с равными доля. По [[Рёберная раскраска двудольного графа#lem2 | нашей лемме]] в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]] и удалим его их графа.
4) Заметим что граф всё остался регулярным, так как степень каждой вершины уменьшилась на 1. Будем повторять процесс, пока в графе есть рёбра.
5) По итогу мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний. Так как на каждой итерации максимальная степень в графе уменьшалась на 1.
6) В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе
Таким образом мы нашли раскраску двудольного графа в <tex>\Delta(G)</tex> цветов и предъявили алгоритм её получения. А по [[Рёберная раскраска двудольного графа#lem1|лемме]] о нижней оценки, меньше цветов использовать нельзя. Следовательно <tex>\chi '(G) = \Delta(G)</tex>
Заметим, что наш жадный алгоритм может проводить кратные рёбра в графе. Однако ни [[Рёберная раскраска двудольного графа#lem2 | наша лемма]], ни [[Теорема Холла | Теорема Холла]] не используют в своём доказательстве отсутствие таковых.
}}
