89
правок
Изменения
Нет описания правки
# Следующим жадным алгоритмом сделаем его <tex>\Delta(G)</tex>-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром
# Мы получили регулярный двудольный граф с равными доля. По лемме о совершенном паросочетании в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]], и удалим из графа.
# Заметим что граф всё ещё остался регулярным, так как степень каждой вершины уменьшилась на <tex>1</tex>. Будем повторять процесс, пока в графе есть рёбра.
# По итогу мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний.
# В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе
