Алгоритм нахождения паросочетания далеко не настолько сложный, насколько сложно сводить задачи к нему.
Начнём с простых примеров.
#Кубики
Дано $n$ кубиков, у каждого из них 6 граней, на каждой гране написана какая-то буква. Дано слово $s$, и требуется каждой букве слова $s$ сопоставить уникальный кубик, так чтобы мы могли повернуть этот кубик и получить нужную нам букву.
Пример — даны три кубика, на гранях которых написаны буквы:
- (a, a, a, a, a, a)
- (а, а, а, а, а, б)
- (а, а, а, б, б, с)
Если задано слово «acb», тогда ответ ровно один: 132.
Решение. Сделаем двудольный граф, одна доля которого — номера кубиков, а другая — номер буквы в слове $s$. Проведем ребра из номера кубика в номер буквы только если мы можем взять этот кубик на эту позицию в строке, то есть если у него есть грань с соответствующей буквой. Теперь ответ — максимальное паросочетание в этом графе.
По определению паросочетания мы не сопоставим ни один кубик нескольким буквам, но так как наше паросочетание — максимально, то мы покроем максимально возможное количество букв.
#Доминошки
Есть прямоугольное поле $n \times m$, которое содержит какие-то выколотые клетки. Надо положить на это поле как можно больше костей домино (прямоугольников размера $1 \times 2$), но с условием, что поверх выколотых полей ничего лежать не должно.
Составим граф, в котором вершины будут полями, а рёбрами будут возможности положить доминошку на два соседних свободных поля. Заметим, что такой граф будет двудольным: можно его покрасить как шахматную доску, и тогда черные клетки будут вершинами первой доли, а белые — второй.
Ответ — максимальное паросочетание в таком графе. Асимптотика с алгоритмом Куна $O(n^2 m^2)$, потому что у нас будет $O(nm)$ вершин и рёбер.
#Покрытие путями DAG
Разберем более сложную задачу, до решения которой самостоятельно додуматься сложно.
Дан ориентированный ациклический граф $G$ (англ. directed acyclic graph, DAG). Требуется покрыть его наименьшим числом путей, то есть найти наименьшее множество простых путей, где каждая вершина принадлежит ровно одному пути.
Построим соответствующие изначальному графу $G$ два двудольных графа $H$ и $\overline{H}$ следующим образом:
- В каждой доле графа $H$ будет по $n$ вершин. Обозначим их через $a_i$ и $b_i$ соответственно.
- Для каждого ребра $(i, j)$ исходного графа $G$ проведём соответствующее ребро $(a_i, b_j)$ в графе $H$.
- Теперь из графа $H$ сделаем граф $\overline{H}$, добавив обратное ребро $(b_i, a_i)$ для каждого $i$.
Если мы рассмотрим любой путь $v_1, v_2, \ldots, v_k$ в исходном графе $G$, то в графе $\overline{H}$ ему будет соответствовать путь $a_{v_1}, b_{v_2}, a_{v_2}, b_{v_3}, \ldots, a_{v_{k-1}}, b_{v_k}$. Обратное тоже верно: любой путь, начинающийся в левой доле $\overline{H}$ и заканчивающийся в правой будет соответствовать какому-то пути в $G$.
Итак, есть взаимно однозначное соответствие между путями в $G$ и путями $\overline{H}$, идущими из левой доли в правую. Заметим, что любой такой путь в $\overline{H}$ — это паросочетание в $H$ (напомним, это $\overline{H}$ без обратных рёбер). Получается, любому пути из $G$ можно поставить в соответствие паросочетание в $H$, и наоборот. Более того, непересекающимся путям в $G$ соответствуют непересекающиеся паросочетания в $H$.
Заметим, что если есть $p$ непересекающихся путей, покрывающих все $n$ вершин графа, то они вместе содержат $r = n - p$ рёбер. Отсюда получаем, что чтобы минимизировать число путей $p$, мы должны максимизировать число рёбер $r$ в них.
Мы теперь можем свести задачу к нахождению максимального паросочетания в двудольном графе $H$. После нахождения этого паросочетания мы должны преобразовать его в набор путей в $G$. Это делается тривиальным алгоритмом: возьмем $a_1$, посмотрим, с какой $b_k$ она соединена, посмотрим на $a_k$ и так далее. Некоторые вершины могут остаться ненасыщенными — в таком случае в ответ надо добавить пути нулевой длины из каждой из этих вершин.
#Минимальное вершинное покрытие
Задача. Назовем вершинным покрытием графа такое множество вершин, что каждое ребро графа инцидентно хотя бы одной вершине из множества. Необходимо найти вершинное покрытие наименьшего размера.
В общем случае это NP-полная задача, но для двудольных графов она имеет достаточно простое решение.
Обозначим за $V_{min}$ наименьшее вершинное покрытие, а за $M$ — максимальное паросочетание в графе. Тогда сразу заметим, что $|V_{min}| \ge |M|$, потому что $M$ — множество независимых ребер. Теперь приведем алгоритм, который строит вершинное покрытие размера ровно $|M|$. Очевидно, оно будет минимальным.
Алгоритм. Мысленно ориентируем ребра графа: ребра из $M$ проведем из правой доли в левую, остальные — из левой в правую, после чего запустим обход в глубину из всех вершин левой доли, не включенных в $M$.
Заметим, что граф разбился на несколько множеств: $L^+, L^-, R^+, R^-$, где «плюсовые» множества — это множества посещенных в процессе обхода вершин. В графе такого вида не бывает ребер $L^+ \rightarrow R^-$ и $L^- \leftarrow R^+$ по очевидным соображениям. Ребер $L^+ \leftarrow R^-$ не бывает, потому что в противном случае паросочетание $M$ не максимальное — его можно дополнить ребрами такого типа.
$$ L^- \cup R^+ = V_{min} $$Понятно, что данное множество покроет все ребра. Осталось выяснить, почему $L^- \cup R^+$. Это верно потому, что $L^- \cup R^+$ покрывает все ребра $M$ ровно один раз (ведь ребра $L^- \rightarrow R^+$ не принадлежат $M$), а также потому, что в нем нет вершин, не принадлежащих $M$ (для $L^-$ это справедливо по определению, для $R^+$ можно провести доказательство от противного с использованием чередующихся цепей).
Упражнение. Подумайте, как это можно применить к решению задачи о нахождении максимального независимого множества.
#Паросочетание минимального веса
Пусть у вершин левой доли есть какие-то веса, и нам нужно набрать максимальное паросочетание минимального веса.
Выясняется, что можно просто отсортировать вершины левой доли по весу и пытаться в таком порядке добавлять их в паросочетание стандартным алгоритмом Куна. Для доказательства этого факта читатель может прочитать про жадный алгоритм Радо-Эдмондса, частным случаем которого является такая модификация алгоритма Куна.
Аналогичную задачу, но когда у ребер есть веса, проще всего решать сведением к нахождению потока минимальной стоимости.