Конспект: паросочетания и покрытия

Понятия

Паросочетание - набор рёбер без общих вершин. Максимальное по включению («некуда добавить») и максимальное по размеру - разные вещи.

Чередующийся путь - рёбра по очереди вне пары и в паре. Дополняющий путь - чередующийся путь между двумя СВОБОДНЫМИ вершинами; его переключение увеличивает паросочетание на единицу.

Теорема Бержа: паросочетание максимально ⟺ дополняющего пути нет.

Вершинное покрытие - набор вершин, накрывающий все рёбра. Независимое множество - вершины, попарно не соединённые ребром.

Цветок - нечётный цикл, найденный ребром между двумя внешними вершинами дерева поиска. Алгоритм Эдмондса - сжимает цветок в основание и ищет дальше; наибольшее паросочетание в любом графе за O(V³), взвешенная версия - тоже O(V³). Жадность по весам - не меньше половины оптимума.

Что унести

сведение к потоку:  s → левые (1),  рёбра графа,  правые → t (1)
                    максимальный поток = максимальное паросочетание
                    целость потока ⇒ ребро берётся целиком, «полработника» не бывает

обратное ребро остаточной сети = ребро, которое сейчас в паре

Алгоритм Куна: для каждой левой вершины - обход в глубину по чередующимся путям, пометки обнуляются ПЕРЕД каждым запуском. Рекурсивный вызов try(match_r[j]) означает «подвинься».

задача	ответ	оговорка
минимальное вершинное покрытие	`\|M\|`	только двудольный граф (Кёниг)
максимальное независимое множество	`\|V\| − \|M\|`	только двудольный
минимальное рёберное покрытие	`\|V\| − \|M\|`	без изолированных вершин
минимальное покрытие путями	`\|V\| − \|M\|`	только ациклический, граф расщепляется на «выходы» и «входы»

Теорема Холла: всю левую долю можно занять ⟺ |N(S)| >= |S| для каждого S слева. В общем случае |M| = |L| − max(|S| − |N(S)|): максимальный дефицит и есть объяснение, почему всех не вышло.

цена	алгоритм
`O(V·E)`	Кун
`O(E·√V)`	Хопкрофт-Карп, он же Диниц на единичных ёмкостях
`O(V³)`	венгерский (веса) и Эдмондс (недвудольный граф)
`O(V²)`	Гейл-Шепли (стабильное паросочетание)

Три разные постановки, которые путают: максимальное по РАЗМЕРУ, минимальное по СТОИМОСТИ (задача о назначениях) и СТАБИЛЬНОЕ (никакая пара не захочет развалить назначение). Спрашивать, что оптимизируется, надо до выбора алгоритма.

Тихие ошибки: не обнулять пометки перед новой левой вершиной (ответ занижен) или обнулять их внутри рекурсии (зацикливание); применять Кёнига и формулу |V| − |M| к недвудольному графу; строить расщеплённый граф для графа с циклами; пускать Куна на недвудольный граф - он не упадёт, он соврёт.

Куда это ведёт

Следующая глава - линейное программирование. Там выяснится, что и поток, и паросочетание - частные случаи одной задачи, а теоремы Кёнига и о максимальном потоке - частные случаи одной двойственности.

Понятия

Что унести

Куда это ведёт

Комментарии

Оставить комментарий