\Section{Минимальное паросочетание}{28 сентября}{Шевченко Илья}

\Subsection{Определения, постановка задачи}

\begin{Def}
(M)atching - множество несмежных рёбер.
\end{Def}
\begin{Def}
Perfect Matching (совершенное паросочетание) - паросочетание размер которого равен размеру наименьшей доли.
\end{Def}
\begin{Def}
(I)ndependent Set - множество попарно неинцедентных вершин.
\end{Def}
\begin{Def}
Vertex (C)over - такое множество вершин, что хотя бы один конец каждого ребра в нём лежит.
\end{Def}

Задача, которую будем решать состоит в максимизации $M$ и $I$ и минимизации $C$.

\begin{Lm}
$I=V\setminus C$,~
$C=V\setminus I$,~
$\max I = V\setminus\min C$
\end{Lm}

\textit{Замечание.}
В произвольном графе задача поиска $\max I$ является NP-трудной. Для поиска максимального паросочетания существуют алгоритм сжатия соцветий за $\O(V^3)$ и алгоритм Вазирани за $\O(E\sqrt{V})$.

\begin{Lm}
Задача поиска максимальной клики эквивалентна задаче поиска $\max I$ в инвертированном графе.
\end{Lm}

\Subsection{Двудольные графы}
\begin{Def}
Чередующийся путь - путь в котором рёбра чередуются в смысле принадлежности паросочетанию.
\end{Def}
\begin{Def}
Дополняющий чередующийся путь - чередующийся путь первая и последняя вершина которого не принадлежат паросочетанию.
\end{Def}
\begin{Lm}
Для того, чтобы паросочетание было совершенным необходимо и достаточно, чтобы не существовало дополняющего чередующегося пути. 
\end{Lm}
\begin{proof}
Если такой путь существует, то инвертируем все рёбра на нём и получим большее паросочетание. 

Докажем теперь, что если такого пути нет, то паросочетание максимальное. Рассмотрим симметрическую разность максимального паросочетание и нашего. Степень каждой вершины в ней не более двух, значит она является объединением циклов и путей. Если есть нечётный путь, в котором первое и последнее ребро принадлежит нашему паросочу, то максимальный можно было бы увеличить по этому пути и вышло бы противоречие. Если есть нечётный путь, в котором первое и последнее ребро принадлежит макс. паросочу, то в нашем графе есть ДЧП, что противоречит предположению.

Значит симм. разность является объединением циклов и чётных путей, а значит в нашем и максимальном паросоче одинаковое количество рёбер, что и требовалось доказать.	
\end{proof}

\Subsubsection{Алгоритм поиска ДЧП}
\begin{code}
dfs(int v)
	used[v] = 1
	for(int x : c[v])
		if mt[x] == -1 or (!u[mt[x]] and dfs(mt[x])):
			mt[x] = v
			return 1
	return 0
\end{code}
С помощью этого алгоритма можно искать паросочетание за $\O(V(V+E))$:
\begin{code}
for v/2
	used <- 0
	for v
		if !covered[v]
			dfs(v)
\end{code}
\Subsubsection{Алгоритм Куна}
\begin{code}
for v in V
	u <- 0
	if dfs(v)
		size++
\end{code}
Для того, чтобы убедиться в корректности этого алгоритма нужно понять, что если мы один раз не смогли найти ДЧП из одной вершины, то больше никогда не сможем. Если рассмотреть изменение в графе после инвертирования ребёр, то несложно понять, что если ДЧП есть сейчас, то она была и раньше.

Кун*:
\begin{code}
for v in V
	if dfs(v)
		size++
\end{code}
Для дальнейшего ускорения Куна можно добавить перед его запуском жадник, который найдёт паросочетание с размером не менее половины максимального:
\begin{code}
for e in E
	if we can add e to M
		add e to M
\end{code}
