Теорема Холла: как проверить, существует ли совершенное паросочетание в двудольном графе?
В задаче нужно понять, можно ли всех слева сопоставить кому-то справа (совершенное паросочетание со стороны левой доли). Слышал про условие Холла «о свадьбах». В чём оно состоит, как им пользоваться в доказательствах и что делать, если просто проверить наличие — запустить паросочетание?
2 ответа
Теорема Холла (о свадьбах): в двудольном графе с долями $L$ и $R$ существует паросочетание, покрывающее всю долю $L$, тогда и только тогда, когда для любого подмножества $S \subseteq L$ выполнено:
$$|N(S)| \ge |S|,$$
где $N(S)$ — множество всех вершин $R$, смежных хотя бы с одной вершиной из $S$. То есть «любая группа женихов знакома суммарно с не меньшим числом невест».
Как пользоваться:
- Для проверки в задаче перебирать все $2^{|L|}$ подмножеств обычно не нужно и дорого — проще запустить алгоритм паросочетания (Кун за $O(VE)$) и проверить, что его размер равен $|L|$. Это эквивалентно условию Холла, но считается за полином.
- Условие Холла нужно для доказательств: когда требуется доказать, что совершенное паросочетание существует (или не существует — тогда предъявляют «дефицитное» подмножество $S$ с $|N(S)| < |S|$).
Полезное следствие (теорема о дефиците): максимальное паросочетание покрывает $|L| - \max_S(|S| - |N(S)|)$ вершин левой доли. Величина $\max_S(|S|-|N(S)|)$ — «дефицит».
Частный случай: в регулярном двудольном графе (все степени равны $k>0$) совершенное паросочетание существует всегда — условие Холла выполняется автоматически. Это популярный факт на олимпиадах.
Дополню связкой с предыдущими теоремами. Холл, Кёниг и max-flow/min-cut — три проекции одного факта:
- Если совершенного паросочетания нет, то по Холлу есть $S$ с $|N(S)|<|S|$.
- Тогда минимальное вершинное покрытие $< |L|$ (берём $N(S)$ и $L\setminus S$), значит по Кёнигу максимальное паросочетание $< |L|$.
Поэтому на практике: хотите число пар — гоните паросочетание; хотите доказать невозможность — ищите нарушающее подмножество $S$ (его, кстати, можно восстановить из конструкции Кёнига — это непокрытые вершины слева и их окрестность).