Рёберная раскраска двудольного графа

Основные определения

Определение:

Рёберной раскраской (англ. Edge colouring) графа [math]G(V, E)[/math] называется отображение [math]\varphi:E \rightarrow \{c_{1} \ldots c_{t}\}[/math] — множество красок такое, что для для любых двух различных рёбер [math]e_{i}, e_{j}[/math] инцидентных одной вершине верно, что [math] \varphi (e_{i}) \neq \varphi (e_{j})[/math].

Определение:

Хроматическим индексом (англ. Chromatic index) [math]\chi '(G)[/math] графа [math]G(V, E)[/math] называется такое минимальное число t, что существует рёберная раскраска графа в t цветов.

Некоторые оценки хроматического индекса

Лемма:

[math]\forall\ G(V, E) : \chi '(G) \geq \Delta (G)[/math]

Доказательство:

[math]\triangleright[/math]

Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно [math]\Delta(G)[/math] рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.

[math]\triangleleft[/math]

Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее [math]\chi '(G)[/math]. А именно что, [math]\forall\ G(V, E) : \Delta (G) \leqslant \chi '(G) \leqslant \Delta (G) + 1[/math]. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.

В данной же статье мы оценим хроматический индекс двудольных графов и предъявим алгоритм их раскраски.

Рёберная раскраска двудольного графа

Лемма:

В двудольном [math]k-[/math]регулярном с одинаковыми по размеру долями графе существует совершенное паросочетание.

Доказательство:

[math]\triangleright[/math]

Возьмём [math]L[/math] — произвольное подмножество левой доли. Рассмотрим подграф образованный [math]L[/math] и множеством всех их соседей из правой доли [math]R[/math]. Все вершины левой доли нашего подграфа будут иметь степень [math]k[/math], а степени вершин правой доли не превосходит [math]k[/math]. Посчитаем количество рёбер [math]m_{L}[/math] в данном подграфе. В силу его двудольности это число будет равняться сумме степеней вершин одной из долей. [math]m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k[/math]. Из этого мы получаем, что [math]|L|\leqslant |R|[/math]. Значит в данном графе выполняется Теорема Холла. Из чего следует, что в нём есть совершенное паросочетание.

[math]\triangleleft[/math]

Теорема:

Существует рёберная раскраска двудольного графа [math]G[/math] в [math]\Delta(G)[/math] цветов. Иными слова для двудольного графа [math]\chi '(G) = \Delta(G)[/math]

Доказательство:

[math]\triangleright[/math]

1) Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством изолированных вершин 2) Следующим жадным алгоритмом сделаем его [math]\Delta(G)-[/math]регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше [math]\Delta(G)[/math] и аналогичную вершину правой доли. Соединим их ребром Докажем, что такой жадный алгоритм всегда выполняет поставленную задачу. Предположим, что это не так, и, не нарушая общности, у нас остались вершины в правой доле степени меньше [math]\Delta(G)[/math], а в левой таких вершин нет. Давайте посчитаем количество рёбер [math]m[/math] в графе. Из левой доли исходит [math]|L| \cdot \Delta(G)[/math] рёбер. В правую же приходит не более [math]|R| \cdot \Delta(G)[/math] рёбер, но так как существует вершина степени меньше [math]\Delta(G)[/math]. То неравенство строгое. Получается [math]|L| \cdot \Delta(G) = m \lt |R| \cdot \Delta(G)[/math]. Но в нашем графе [math]|L| = |R|[/math]. Следовательно [math]\Delta(G) \lt \Delta(G)[/math], что приводит нас к противоречию 3) Мы получили регулярный двудольный граф с равными доля. По нашей лемме в таком графе есть совершенное паросочетание. Найдём его, например алгоритмом Куна и удалим его их графа. 4) Заметим что граф всё остался регулярным, так как степень каждой вершины уменьшилась на 1. Будем повторять процесс, пока в графе есть рёбра. 5) По итогу мы разобьём рёбра графа на [math]\Delta(G)[/math] совершенных паросочетаний. Так как на каждой итерации максимальная степень в графе уменьшалась на 1. 6) В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе Таким образом мы нашли раскраску двудольного графа в [math]\Delta(G)[/math] цветов и предъявили алгоритм её получения. А по лемме о нижней оценки, меньше цветов использовать нельзя. Следовательно [math]\chi '(G) = \Delta(G)[/math] Заметим, что наш жадный алгоритм может проводить кратные рёбра в графе. Однако ни наша лемма, ни Теорема Холла не используют в своём доказательстве отсутствие таковых.

[math]\triangleleft[/math]