Алгоритм Эдмондса (Блоссом): Максимальное паросочетание в произвольных графах
Найти идеальные пары в двудольном графе (например, распределить таксистов по заказам или рабочих по станкам) довольно просто — с этим блестяще справляется алгоритм Куна, использующий поиск увеличивающих цепей. Но что делать, если граф не разделен на две независимые доли? Представьте задачу: разбить 100 студентов на пары для совместного проекта, где ребро означает, что два студента согласны работать вместе. Это задача поиска максимального паросочетания в произвольном графе. Обычный алгоритм Куна здесь зациклится и сломается. Решение в 1965 году нашел Джек Эдмондс.
Проблема произвольных графов кроется в существовании циклов нечетной длины (например, треугольников). Если алгоритм Куна при поиске чередующейся цепи (состоящей поочередно из свободных и занятых в паросочетании ребер) зайдет в такой цикл, он начнет ходить по кругу, не зная, из какой вершины цикла выйти, чтобы продолжить путь к свободной вершине.
Эдмондс разработал гениальную математическую абстракцию, известную как Алгоритм "Цветка" (Blossom Algorithm). Терминология алгоритма весьма поэтична:
- Стебель (Stem): Чередующийся путь, который ведет от корневой (свободной) вершины к основанию нечетного цикла.
- Цветок (Blossom): Тот самый злополучный цикл нечетной длины, состоящий из
2k + 1ребер, из которыхkребер принадлежат текущему паросочетанию. Вершина, где стебель соединяется с цветком, называется базой.
Суть алгоритма Эдмондса заключается в сжатии (Contraction). Как только алгоритм при обходе графа (через BFS) обнаруживает цветок (нечетный цикл), он берет все вершины этого цикла и математически "схлопывает" их в одну гигантскую супервершину! Все внешние ребра, которые вели к любой из вершин цветка, теперь просто ведут к этой новой супервершине.
После сжатия цветка граф становится меньше, и алгоритм продолжает поиск увеличивающей цепи в этом редуцированном графе. Если увеличивающая цепь найдена и она проходит через супервершину, алгоритм выполняет обратную операцию — разворачивание цветка (Lifting). Он восстанавливает исходный цикл и маршрутизирует путь внутри него так, чтобы цепь осталась чередующейся. За счет нечетности цикла такой корректный проход гарантированно существует.
Этот процесс сжатия и разворачивания продолжается рекурсивно. Алгоритм Блоссома стал исторической вехой в информатике. Сама статья Эдмондса «Пути, деревья и цветы» была одной из первых в истории, где явно обсуждалась концепция "хороших" алгоритмов (полиномиального времени, класса P) в противовес "плохим" алгоритмам экспоненциального перебора.
