Теорема Холла: как проверить, существует ли совершенное паросочетание в двудольном графе?

Question

В задаче нужно понять, можно ли всех слева сопоставить кому-то справа (совершенное паросочетание со стороны левой доли). Слышал про условие Холла «о свадьбах». В чём оно состоит, как им пользоваться в доказательствах и что делать, если просто проверить наличие — запустить паросочетание?

Лев Степанов · Accepted Answer

Теорема Холла (о свадьбах): в двудольном графе с долями $L$ и $R$ существует паросочетание, покрывающее всю долю $L$, тогда и только тогда, когда для любого подмножества $S \subseteq L$ выполнено: $$|N(S)| \ge |S|,$$ где $N(S)$ — множество всех вершин $R$, смежных хотя бы с одной вершиной из $S$. То есть «любая группа женихов знакома суммарно с не меньшим числом невест». Как пользоваться: - Для проверки в задаче перебирать все $2^{|L|}$ подмножеств обычно не нужно и дорого — проще запустить алгоритм паросочетания (Кун за $O(VE)$) и проверить, что его размер равен $|L|$. Это эквивалентно услов…

Игорь Жуков · Answer

Дополню связкой с предыдущими теоремами. Холл, Кёниг и max-flow/min-cut — три проекции одного факта:

Если совершенного паросочетания нет, то по Холлу есть $S$ с $|N(S)|<|S|$ .
Тогда минимальное вершинное покрытие $< |L|$ (берём $N(S)$ и $L\setminus S$ ), значит по Кёнигу максимальное паросочетание $< |L|$ .

Поэтому на практике: хотите число пар — гоните паросочетание; хотите доказать невозможность — ищите нарушающее подмножество $S$ (его, кстати, можно восстановить из конструкции Кёнига — это непокрытые вершины слева и их окрестность).

Теорема Холла: как проверить, существует ли совершенное паросочетание в двудольном графе?

2 ответа

Ваш ответ