%\author{Савон Юлия}
%\date{22 марта 2016}
\Section{Обобщение Куна на произвольные графы}{26 марта}{Савон Юлия}
\Subsection{Матрица Татта}

Полиномиальный алгоритм($\O(V^3)$), выдающий с некоторой погрешностью результат -- существует ли совершенное паросочетание в произвольном графе.

В ячейках соответствующим рёбрам стоят рандомные значения(для $x_{ij}$, где $0 < i < j \le n$).

Матрица антисимметрична(т.е. в оставшихся $x_{ij}$, где $0 < j < i \le n$), стоят значения противоположные $x_{ji}$.

Для отсутствующих рёбер поставим 0.

\begin{Thm}{Татта:}
	В графе G $\exists$ совершенное паросочетание $\Leftrightarrow$ $[det A \neq 0]$
\end{Thm}

Теорему оставляем без доказательства и хотим сказать, что вероятность ошибки $\leqslant \frac{1}{p}$

\Subsection{Алгоритм поиска совершенного паросочетания:}

\lstinputlisting{savon/ideal_pairs.cpp}

Работает за $\O((n - 1)!!)$

\Subsection{Upgrade Куна почти всегда работающего на произвольном графе:}

Рандомно выбираем вершины из которых ищем путь, перемешиваем рёбра перед тем как запускать dfs, если Кун пытается создать нечётный цикл -- не идём по ребру.

$\exists$ тесты на которых вероятность успеха порядка $2^{-\frac{n}{2}}$, но их не очень много.

Можно запускать такое решение со счётчиком времени ``Пока не TL''.

\Subsection{Задача: Класифицировать рёбра на обязательно/возможно лежащие в max паросочетании для двудольного графа:}

1)Для начала найдём max паросочетание $\O(VE)$ (умеем) $~>$ $\O(E \sqrt{V})$ (какой-то существующий) -- M

2)Теперь рассмотрим какое-нибудь другое максимальное паросочетание  -- P

Теперь рассмотрим мн-во рёбер лежащих ровно в одном из них. Заметим, что такой набор рёбер образует граф, в котором у каждой вершины стпень $\leqslant 2$, кроме того в нём есть только чётные циклы (из-за двудольности) и только пути чётной длины(т.к. в случае пути нечётной длины, конвертнув этот кусочек мы увеличим на 1 размер паросочетания второго графа). 

Значит каждое ребро которое может лежать или не лежать, должно содержаться в цикле чётной длины с чередующимися (взяли/не взяли в паросочетание M) рёбрами. Аналогично, если ребро лежит на таком цикле, то мы можем конвертнуть цикл и получить опять же максимальное паросочетание.

\textbf{Поиск циклов и путей чётной длины в двудольном графе:} 

\begin{itemize}
\item {\bf Циклы.  $\O(E)$}\\
  Если 2 ребра лежат в одной компоненте сильной связности, то существует чётный цикл содержащий их обоих. Соответственно ищем одним dfs-ом подходящие и помечаем рёбра.
\item {\bf Пути. $\O(E)$}\\
  Запускаемся от всех вершин у которых нет рёбер найденого паросочетания, всё до чего они дошли по чередующимся рёбрам является нужными путями, поэтому сразу помечаем вершины.
\end{itemize}
