Алгоритм Куна: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Идея== Мы только, что доказали утверждение о том, что в максимальном паросочетание нет у...»)
 
Строка 2: Строка 2:
  
 
Мы только, что доказали утверждение о том, что в максимальном паросочетание нет удлиняющих цепей, тогда давайте просто изначально возьмем пустое паросочетание и каждый раз, пока есть удлиняющие цепи будем инвертировать их.
 
Мы только, что доказали утверждение о том, что в максимальном паросочетание нет удлиняющих цепей, тогда давайте просто изначально возьмем пустое паросочетание и каждый раз, пока есть удлиняющие цепи будем инвертировать их.
 +
==Утверждение==
  
Заметим, что через одну вершину может проходить только одна удлиняющая цепь. Тогда мы можем найти все удлиняющие цепи, запуская поиск удлиняющей цепи из каждой вершины. Искать удлиняющие цепи мы умеем DFS-ом.
+
Если из вершины $x$ не существует дополняющей цепи относительно паросочетания $M$ и паросочетание $M^{/prime}$  получается из $M$ изменением вдоль дополняющей цепи, тогда из $x$ не существует дополняющей цепи в $M^{\prime}$.
 +
 
 +
==Следствие==
 +
 
 +
Тогда мы можем найти все удлиняющие цепи, запуская поиск удлиняющей цепи из каждой вершины. Искать удлиняющие цепи мы умеем DFS-ом.
  
 
==Алгоритм==
 
==Алгоритм==

Версия 14:11, 12 февраля 2020

Идея

Мы только, что доказали утверждение о том, что в максимальном паросочетание нет удлиняющих цепей, тогда давайте просто изначально возьмем пустое паросочетание и каждый раз, пока есть удлиняющие цепи будем инвертировать их.

Утверждение

Если из вершины $x$ не существует дополняющей цепи относительно паросочетания $M$ и паросочетание $M^{/prime}$ получается из $M$ изменением вдоль дополняющей цепи, тогда из $x$ не существует дополняющей цепи в $M^{\prime}$.

Следствие

Тогда мы можем найти все удлиняющие цепи, запуская поиск удлиняющей цепи из каждой вершины. Искать удлиняющие цепи мы умеем DFS-ом.

Алгоритм

Давайте пройдемся по всем вершинам первой доли, проверяя насыщена ли текущая вершина(взято ли в паросочетание ребро, инцидентное ей), если насыщена - пропускаем, иначе пробуем насытить следующим DFS-ом:

 1 bool dfs (int v) {
 2     if (used[v]) {
 3         return false;
 4         used[v] = true;
 5         for (auto to : g[v]) {
 6             if (mt[to] == -1 || dfs(mt[to])) {
 7                 mt[to] = v;
 8                 return true;
 9 	    }
10     }
11     return false;
12 }

В DFS-е мы проверяем все ребра из вершины и если есть вершина, которая еще не насыщена, то мы нашли удлиняющую цепь, иначе запустимся и проверим, есть ли удлиняющая цепь и там.

Асимптотика

Мы запускаем DFS из всех вершин, то есть итоговая асимптотика - $O(N \cdot (N + M)$

Оптимизации

Несмотря на достаточно быструю константу(очень часто алгоритм Куна работает настолько быстро, что заходит и при $N = 2e5$, есть несколько его основных оптимизаций :

1) Брать не пустое паросочетание, а например набирать его жадно.

2) Очень часто можно столкнуться с тем, что не все вершины посещаются в DFS и поэтому каждый раз обнулять used - долго и можно просто хранить int в used и проверять что он равен номеру вершины, из которой мы запустили DFS :

 1 bool dfs (int v, int now) {
 2     if (used[v] == now) {
 3         return false;
 4         used[v] = true;
 5         for (auto to : g[v]) {
 6             if (mt[to] == -1 || dfs(mt[to], now)) {
 7                 mt[to] = v;
 8                 return true;
 9 	    }
10     }
11     return false;
12 }

Что дальше

Существует способ искать паросочетания быстрее($E\sqrt{V}$)(Потоки), также существуют способы искать взвешенное паросочетания и паросочетания не в двудольных графах(Сжатие соцветий)



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin