Теорема Кёнига: как найти минимальное вершинное покрытие в двудольном графе через паросочетание?
В задаче нужно выбрать минимум вершин так, чтобы каждое ребро было покрыто (минимальное вершинное покрытие). Граф двудольный. Слышал про теорему Кёнига, что это равно максимальному паросочетанию. Как это понять и, главное, как восстановить само покрытие?
2 ответа
Теорема Кёнига: в двудольном графе размер минимального вершинного покрытия равен размеру максимального паросочетания. (В общих графах это неверно!)
Восстановление покрытия (конструкция Кёнига). Пусть посчитано максимальное паросочетание $M$. Доли $L$ и $R$.
- Возьмём все ненасыщенные (свободные) вершины левой доли.
- Запускаем чередующийся обход: из свободной левой вершины идём по свободному ребру в $R$, оттуда по ребру паросочетания обратно в $L$, и т.д. Помечаем все достижимые вершины (множество $Z$).
- Минимальное вершинное покрытие = (вершины $L$, которые НЕ в $Z$) $\cup$ (вершины $R$, которые в $Z$).
// matchR[r] = пара справа, matchL[l] = пара слева (-1 = свободна)
vector<char> visL(nL,0), visR(nR,0);
function<void(int)> dfs = [&](int l){
visL[l]=1;
for(int r : adj[l]) if(matchR[r]!=l && !visR[r]){ // свободное ребро
visR[r]=1;
if(matchR[r]!=-1 && !visL[matchR[r]]) dfs(matchR[r]);
}
};
for(int l=0;l<nL;l++) if(matchL[l]==-1) dfs(l); // из свободных слева
// покрытие: { l : !visL[l] } ∪ { r : visR[r] }
Размер этого множества как раз равен $|M|$.
Бонус: максимальное независимое множество в двудольном графе = (все вершины) минус (минимальное вершинное покрытие). Это прямое следствие, потому что дополнение вершинного покрытия — всегда независимое множество.
Идея, почему конструкция работает, через минимальный разрез. Если построить сеть из паросочетания (как для max-flow), то минимальный разрез этой сети по теореме max-flow/min-cut равен потоку = $|M|$. А рёбра минимального разреза идут либо из $s$ в непосещённую левую, либо из посещённой правой в $t$ — это ровно те вершины $L\setminus Z$ и $R\cap Z$. То есть теорема Кёнига — это max-flow/min-cut, переписанная для двудольного случая. Если уже умеете восстанавливать минимальный разрез через достижимость из $s$ — получите покрытие тем же кодом.