Паросочетание: та же задача о потоке, другими словами

Если ты умеешь сводить двудольное паросочетание к потоку, отличаешь «нельзя расширить» от «максимальное» и знаешь теорему Бержа про дополняющие пути, листай до «Теперь сам».

Как думаешь, почему жадность ошибается

Три работника и три задачи. Аня умеет делать только первую задачу, Борис - первую и вторую, Вера - вторую и третью. Жадность идёт по списку: Аня берёт первую, Борис - вторую, Вера... третью. Все трое при деле, повезло.

Теперь поменяй порядок: пусть первым в списке идёт Борис. Он берёт первую задачу, Аня остаётся без работы (она больше ничего не умеет), Вера берёт вторую. Двое из трёх. Тот же граф, тот же жадный алгоритм - и ответ хуже на единицу только из-за порядка. Что надо уметь, чтобы такого не случалось?

На что это похоже

Пересадка гостей за столом. Расселил всех как попало, а потом заметил, что двое хотят поменяться местами, и после обмена становится лучше обоим. Одиночная перестановка тут не спасает - меняться приходится цепочкой: этот пересядет на место того, тот на место третьего, и в конце освободится место для гостя, который вообще стоял. Такая цепочка и называется дополняющим путём.

Механизм: сведение к потоку и чередующиеся пути

двудольный граф: левая доля L, правая доля R, рёбра только между долями

сеть:  s → каждая вершина L    пропускная способность 1
       рёбра графа L → R       пропускная способность 1 (или бесконечность - не важно)
       каждая вершина R → t    пропускная способность 1

максимальный поток = максимальное паросочетание

Почему это работает: пропускная способность 1 на рёбрах из истока означает «каждый работник берёт не больше одной задачи», а на рёбрах в сток - «каждую задачу берёт не больше одного работника». Поток целый (пропускные способности целые), поэтому по каждому ребру идёт либо 0, либо 1 - никаких «половин работника».

чередующийся путь - путь, где рёбра по очереди: не в паросочетании, в паросочетании,
                    не в паросочетании, ...

дополняющий путь  - чередующийся путь, который НАЧИНАЕТСЯ и КОНЧАЕТСЯ в свободных вершинах
                    (в такой цепочке рёбер «вне пары» на одно больше)

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

Если дополняющий путь найден, его «переключают»: рёбра вне паросочетания берут в пару, рёбра из паросочетания - убирают. Путь начинался и кончался свободными вершинами, значит взятых рёбер на одно больше - паросочетание выросло ровно на единицу.

Правило

Паросочетание - набор рёбер без общих вершин. МАКСИМАЛЬНОЕ ПО ВКЛЮЧЕНИЮ («жадное, некуда добавить ребро») и МАКСИМАЛЬНОЕ ПО РАЗМЕРУ - разные вещи, и первое бывает меньше второго. Двудольное паросочетание сводится к потоку: исток → левые (1), рёбра графа, правые → сток (1); целость потока даёт честный ответ. Паросочетание максимально тогда и только тогда, когда нет дополняющего пути (теорема Бержа), а переключение такого пути увеличивает паросочетание ровно на единицу.

Разбор: как дополняющий путь чинит жадность

Вернёмся к работникам. Слева А, Б, В, справа задачи 1, 2, 3. Рёбра: А-1, Б-1, Б-2, В-2, В-3.

Жадность в неудачном порядке дала пары Б-1 и В-2, Аня свободна, задача 3 свободна. Ищем дополняющий путь из свободной вершины А:

А —(не в паре)— 1 —(в паре)— Б —(не в паре)— 2 —(в паре)— В —(не в паре)— 3
 свободна                                                          свободна

Рёбра чередуются, концы свободны - это дополняющий путь. Переключаем: А-1 берём, Б-1 убираем, Б-2 берём, В-2 убираем, В-3 берём.

было:  Б-1, В-2                     размер 2
стало: А-1, Б-2, В-3                размер 3

Заметь, что произошло: никого не «выгнали». Борис и Вера остались при работе, просто сдвинулись, и освободившееся место досталось Ане. Именно поэтому жадность и ошибается - она умеет только добавлять, а нужно уметь ПЕРЕСТАВЛЯТЬ.

Разбор: почему это тот же поток

Сложим ту же сеть по рецепту из механизма. Исток s, работники А, Б, В, задачи 1, 2, 3, сток t.

s→А=1  s→Б=1  s→В=1
А→1=1  Б→1=1  Б→2=1  В→2=1  В→3=1
1→t=1  2→t=1  3→t=1

Жадный поток s→Б→1→t и s→В→2→t имеет величину 2. Дополняющий путь в ОСТАТОЧНОЙ сети выглядит так: s → А → 1 → Б → 2 → В → 3 → t, где 1 → Б и 2 → В - обратные рёбра (по ним уже идёт поток). Величина узкого места - единица, поток становится 3.

Сравни с предыдущим разбором: это буквально тот же чередующийся путь, только записанный через остаточную сеть. Обратное ребро потока и «ребро, которое сейчас в паре» - одно и то же. Поэтому все теоремы про потоки автоматически работают для паросочетаний, а алгоритм Куна из следующего урока - это Форд-Фалкерсон, записанный без слова «поток».

Что ломается без этого

Первое: путать «максимальное по включению» и «максимальное по размеру». Жадный набор нельзя расширить, но переставить - можно, и именно это даёт прирост. Второе: сводить к потоку, но ставить на рёбрах из истока пропускную способность больше единицы - тогда один работник получит две задачи, и ответ перестанет быть паросочетанием. Третье: искать дополняющий путь из ЗАНЯТОЙ вершины: путь обязан начинаться в свободной, иначе переключение сломает существующую пару и размер не вырастет. Четвёртое: применять всё это к произвольному, не двудольному графу. Теорема Бержа верна и там, но искать дополняющий путь обходом уже нельзя: мешают нечётные циклы, и нужен алгоритм Эдмондса со сжатием «цветков». Пятое: думать, что максимальное паросочетание единственно, - их обычно много, и алгоритмы выдают разные, но одного размера.

Зачем это в работе

Любая задача вида «сопоставить одно с другим, и каждому не больше одного» - это паросочетание: заявки на исполнителей, доклады по залам, студенты по проектам, водители по маршрутам, резюме по вакансиям. Сюда же - задачи, где сопоставление неочевидно: проверка расписания на выполнимость, распределение переменных по регистрам в компиляторе, склейка кадров в трекинге объектов. А ещё этот приём - типовой способ доказать, что задача РЕШАЕТСЯ быстро: если получилось свести к двудольному паросочетанию, значит есть полиномиальный алгоритм, и не надо ни перебора, ни эвристик.

Теперь сам

Граф: слева A, B, C, справа 1, 2, 3. Рёбра: A-1, A-2, B-1, C-2, C-3. Жадность взяла A-1 и C-2. Найди дополняющий путь и увеличь паросочетание.

B —(не в паре)— 1 —(в паре)— A —(не в паре)— 2 —(в паре)— C —(не в паре)— 3