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