Кёниг, покрытие и независимое множество

Теорема Кёнига. В двудольном графе размер минимального вершинного покрытия равен размеру максимального паросочетания.

Вершинное покрытие — набор вершин, такой что у каждого ребра хотя бы один конец в наборе.

Неравенство в одну сторону очевидно: рёбра паросочетания попарно не пересекаются, поэтому покрыть их все меньше чем $|M|$ вершинами нельзя. Содержательно то, что покрытие такого размера существует — и строится явно.

Построение

Возьмём максимальное паросочетание $M$ и запустим обход из свободных вершин доли $A$ по чередующимся путям: из левой доли идём по рёбрам не из $M$, из правой возвращаемся по рёбрам из $M$. Пусть $L$ и $R$ — посещённые вершины левой и правой доли.

$$C = (A \setminus L) \cup R.$$

for (int u = 0; u < n; u++) if (matchLeft[u] == -1) { seenLeft[u] = 1; queue.push_back(u); }
for (size_t head = 0; head < queue.size(); head++) {
    int u = queue[head];
    for (int v : adj[u]) {
        if (seenRight[v] || matchLeft[u] == v) continue;   // только рёбра не из M
        seenRight[v] = 1;
        int w = matchRight[v];
        if (w != -1 && !seenLeft[w]) { seenLeft[w] = 1; queue.push_back(w); }
    }
}

Почему это покрытие. Пусть ребро $(a, b)$ не покрыто: $a \in L$, $b \notin R$. Из $a$ обход обязан был пойти по этому ребру. Если оно не из $M$, то $b$ попала бы в $R$. Если из $M$, то $a$ была посещена приходом по нему из $b$, то есть $b \in R$. Противоречие.

Почему размер равен $|M|$. Каждая вершина из $C$ покрыта паросочетанием: свободные вершины слева все лежат в $L$, а свободная вершина справа в $R$ означала бы увеличивающий путь. И никакое ребро $M$ не даёт в $C$ оба конца: если $b \in R$ достигнута, её пара попала в $L$ и в $C$ не входит.

Обход обязан начинаться именно со свободных вершин. Запустив его из всех, вы получите покрытие, но не минимальное.

Что отсюда следует

Максимальное независимое множество. Дополнение независимого множества — это вершинное покрытие, поэтому в любом графе $|I| = V - |C|$, а в двудольном

$$|I| = V - |M|, \qquad I = L \cup (B \setminus R).$$

В произвольном графе задача NP-трудна; двудольность и есть то, что делает её полиномиальной.

Минимальное рёберное покрытие (набор рёбер, задевающий все вершины; требует отсутствия изолированных вершин) равно $V - |M|$ — теорема Галлаи. Построение: паросочетание плюс по одному ребру к каждой непокрытой вершине.

Недостача по Холлу: $n - |M| = \max_S (|S| - |N(S)|)$. Подставьте $S = A \setminus C$ и посчитайте.

Ориентация: какие рёбра могут быть в паросочетании

Построим орграф $D$: рёбра не из $M$ направим слева направо, рёбра из $M$ — справа налево. Тогда чередующиеся пути становятся обычными путями, и на два естественных вопроса есть ответы.

Ребро $(a, b)$ входит хотя бы в одно максимальное паросочетание, если оно из $M$, либо $a$ и $b$ лежат в одной компоненте сильной связности $D$ (чередующийся цикл через ребро), либо $a$ достижима из свободной вершины левой доли, либо из $b$ достижима свободная вершина правой доли.

Три условия, а не одно: добавив ребро, приходится выкинуть два ребра паросочетания, и восстановить размер можно либо циклом, либо пристроив одну из освободившихся вершин к свободной. Ограничиться проверкой компоненты — типичная ошибка.

Ребро входит во все максимальные паросочетания, если оно из $M$ и не выполнено ни одно из трёх условий: концы в одной компоненте сильной связности; из левого конца достижима свободная вершина справа; правый конец достижим из свободной вершины слева.

Оба критерия — прямое следствие рассуждения про симметрическую разность: другое максимальное паросочетание отличается от $M$ чередующимися циклами и путями, начинающимися в свободных вершинах.

Где теорема ломается

Треугольник: максимальное паросочетание — одно ребро, минимальное покрытие — две вершины. Равенство держится на отсутствии нечётных циклов, то есть ровно на двудольности. В общем графе паросочетание всё ещё ищется за полином, а вершинное покрытие — уже NP-трудная задача.