1632
правки
Изменения
м
В данной же статье мы оценим хроматический индекс двудольных графов и предъявим алгоритм их раскраски.
rollbackEdits.php mass rollback
{{Определение
|id = edge_colouring
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:</tex> из множества рёбер <tex>E \rightarrow </tex> во множество красок <tex>\{c_{1} \ldots c_{t}\}</tex> {{---}} ''множество красок'' такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex>, инцидентных одной вершине, верно <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.
}}
}}
Заметим, что в теории графов доказывается более строгое неравенство<ref>http://math.uchicago.edu/~may/REU2015/REUPapers/Green.pdf</ref>, ограничивающее <tex>\chi '(G)</tex>. А именно то, что <tex>\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \leqslant \Delta (G) + 1</tex>. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.
== Рёберная раскраска двудольного графа ==
# Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством [[Основные определения теории графов#isolated_vertex | изолированных вершин]];
# Следующим жадным алгоритмом сделаем его <tex>\Delta(G)</tex>-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром;
# Мы получили регулярный двудольный граф с равными долядолями. По лемме о совершенном паросочетании в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]], и удалим из графа;
# Заметим, что граф всё ещё остался регулярным, так как степень каждой вершины уменьшилась на <tex>1</tex>. Будем повторять процесс, пока в графе есть рёбра;
# В итоге мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний;
