Теория графов в планировании: задача о максимальном паросочетании и алгоритм Эдмондса

Математическая модель задачи начинается с определения паросочетания: это набор ребер графа, не имеющих общих смежных вершин (ни один узел не может принадлежать более чем одному ребру из набора). В двудольных графах (где множество вершин четко разделено на две изолированные группы, например, работники и станки, и связи возможны только между группами) задача поиска максимального паросочетания виртуозно сводится к задаче о максимальном потоке. Для этого в сеть фиктивно добавляются глобальный исток и сток с единичной пропускной способностью дуг. Запустив классический алгоритм Форда-Фалкерсона, аналитик получает абсолютно точный ответ: максимальный целочисленный поток, проходящий через сеть, однозначно определяет максимальное количество идеальных пар, которые можно сформировать на заводе.

Однако реальные проблемы часто не обладают двудольной структурой. В задаче об обмене почками или формировании экипажей космонавтов любой участник системы может потенциально стать партнером любого другого участника (граф общего вида). Наличие нечетных циклов (треугольников, пятиугольников) в таких графах разрушает логику двудольных потоковых алгоритмов. Попытка применить жадный алгоритм (просто соединять первые попавшиеся пары) неизбежно приводит к тупику, когда множество узлов остаются не у дел, хотя перестройка существующих пар позволила бы интегрировать их в систему. Вычислительная сложность поиска абсолютного максимума в графах общего вида долгое время считалась непреодолимой.

Абсолютный математический прорыв совершил Джек Эдмондс в 1965 году, опубликовав свой алгоритм сжатия цветков (Blossom Algorithm). Этот алгоритм стал шедевром дискретной математики. В основе алгоритма лежит концепция увеличивающего пути — цепочки ребер, которая начинается и заканчивается в свободных (не спаренных) вершинах, причем ребра в ней строго чередуются: не из паросочетания, из паросочетания, снова не из паросочетания и так далее. Если такой путь найден, алгоритм математически инвертирует статусы всех его ребер, увеличивая общее количество сформированных пар ровно на единицу. Теорема Бержа строго доказывает, что если увеличивающего пути в графе не существует, то текущее паросочетание гарантированно является глобально максимальным.

Гениальность метода Эдмондса заключается в обработке нечетных циклов, которые блокируют поиск увеличивающего пути. Как только алгоритм, строя дерево поиска, натыкается на нечетный цикл (называемый цветком или Blossom), он совершает топологическое схлопывание. Весь этот нечетный цикл стягивается (сжимается) в одну фиктивную супер-вершину, и алгоритм продолжает поиск в новом, упрощенном графе. Если увеличивающий путь будет найден через эту супер-вершину, алгоритм разворачивает цветок обратно и восстанавливает истинный путь через исходные узлы графа. Этот виртуозный алгебраический трюк обеспечил решение сложнейшей комбинаторной задачи за полиномиальное время (пропорционально кубу числа вершин), открыв дорогу к автоматизации распределения сотен тысяч донорских органов и оптимизации коммуникационных сетей в современных дата-центрах.