\Section{Потоки (быстрые)}{25 сентября}{Сергей Копелиович}

\Subsection{Алгоритм Диница}

У нас уже есть алгоритм Эдмондса-Карпа, ищущий $\O(VE)$ путей за $\O(E)$ каждый.

Построим сеть кратчайших путей, расстояние $s \leadsto t$ обозначим $d$.

Слоем $A_i$ будем называть вершины на расстоянии $i$ от $s$.

Э.К. сперва найдёт сколько-то путей длины $d$, затем расстояние $s \leadsto t$ увеличится.

\begin{Lm}
Пока $\exists$ путь длины $d$, он имеет вид $s = v_0 \in A_0, v_1 \in A_1, v_2 \in A_2, \dots, t = v_d \in A_d$
\end{Lm}
\begin{proof}
В первый момент это очевидно. Затем в $G_f$ будут появляться новые рёбра -- обратные к $v_i \to v_{i+1}$.
Все такие рёбра идут назад по слоям $\SO$ новых рёбер идущих вперёд по слоям не образуется $\SO$ 
каждый раз при поиске пути единственный способ за $d$ шагов из $s$ попасть в $t$ -- $d$ раз по одному из старых рёбер идти ровно в следующий слой.
\end{proof}

Научимся искать все пути длины $d$ за $\O(E + d k_d)$, где $k_d$ -- количество путей.

\down
Выделим множество $E'$ -- рёбра $A_i \to A_{i+1}$ в $G_f$.
Будем запускать dfs по $E'$.\\
Модифицируем dfs: если пройдя по рёбру $e$, dfs не нашёл путь до $t$, он удалит $e$ из $E'$.\\
Каждый из $k_d$ dfs-ов сделал $d$ успешных шагов и $x_i$ неуспешных, но $\sum x_i \le E$, так как после каждого неуспешного шага мы удаляем ребро из $E'$.
\begin{code}
void dfs(int v) {
	while (head`\color{black}{'}`[v] != -1) {
		Edge &e = edges[head`\color{black}{'}`[v]];
		if (e.f < e.c && (e.b == t || dfs(e.b))) {
			// `\color{black}{нашли путь}`
		}
		head`\color{black}{'}`[v] = e.next;
	}
}
\end{code}
Заметьте, что массив пометок вершин, обычный для любого dfs, тут можно не использовать.

\THE{Алгоритм Диница}

Состоит из фаз вида: 

(1) запустить bfs, который построил слоистую сеть и нашёл $d$.

(2) пока в слоистой сети есть путь длины $d$, \\ \hspace*{1.2em} найдём его dfs-ом и толкнём по нему $\min_e(c_e-f_e)$ единиц потока.

\begin{Thm}\label{thm@dinic1}
Время работы алгоритма Диница $\O(V^2E)$.\end{Thm}
\begin{proof}
Фаз всего не более $V$ штук, так как после каждой $d \uparrow$\\
Фаза с расстоянием $d$ работает за $\O(E + d \cdot k_d)$.
\begin{smallformula}
$$\sum (E + d \cdot k_d) \le VE + V \sum k_d \le VE + V(VE)$$
\end{smallformula}
 Последнее известно из алгоритма Эдмондса-Карпа.
\end{proof}

\pagebreak
\vspace*{-1.5em}
\THE{Алгоритм Диница с масштабированием потока}

Масштабирование потока -- не только конкретный алгоритм, но и общая идея:
\begin{code}
for (int k = `\color{black}{$\log$}` U; k >= 0; k--)
	`\color{black}{пускаем поток на графе с пропускными способностями $(c_e - f_e) / 2^k$}`
\end{code}

Давайте искать поток именно алгоритмом Диница.
\begin{Thm}Время работы алгоритма Диница с масштабированием $\O(VE \log U)$.\end{Thm}
\begin{proof}
Каждая из фаз масштабирование -- алгоритм Диница, который найдёт не более $E$ путей
и работает за время (делаем то же, что и в теореме \autoref{thm@dinic1}):
\begin{smallformula}
$$\sum (E + d \cdot k_d) \le VE + V \sum k_d \le VE + VE = \O(VE)$$
\end{smallformula}
Значит, суммарно все $\log U$ фаз отработают за $\O(VE \log U)$.
\end{proof}

\vspace*{-0.5em}
\Subsection{Алгоритм Хопкрофта-Карпа}

\up
\begin{Lm}
В единичной сети ($c_e \equiv 1$) фаза Диниц работает за $\O(E)$
\end{Lm}

\vspace*{-1.0em}
\begin{proof}
Если dfs пройдёт по ребру $e$, он его в любом случае удалит -- и если не найдёт по нему путь, и если найдёт по нему путь: $(c_e = 1) \SO e$ насытится.
\end{proof}

Мы уже умеем искать паросочетание за $\O(VE)$ через потоки.

Давайте в том же графе запустим алгоритм Диница.

\begin{Thm}
Число фаз Диница на сети для поиска паросочетание не более $2 \sqrt{V}$.
\end{Thm}

\vspace*{-1.0em}
\begin{proof}
Сделаем первые $\sqrt{V}$ фаз, получили поток $f$, посмотрим на $G_f$.\\
В остаточной сети все пути имеют длину хотя бы $\sqrt{V}$.
Вспомним биекцию между доппутями в $G_f$ и ДЧП для паросочетания $\SO$
все ДЧП тоже имеют длину хотя бы $\sqrt{V}$.\\
Пусть поток $f$ задаёт паросочетание $P$, рассмотрим максимальное $M$. \\
$M \triangledown P$  содержит $k=|M|-|P|$ неперескающихся ДЧП, каждый длины $\ge \sqrt{V} \SO$ \\
$k \le \sqrt{V} \SO$ 
Динице осталось найти $\le \sqrt{V}$ путей. \\
Осталось заметить, что за каждую фазу Диниц находит хотя бы один путь.
\end{proof}

\up
\THE{Алгоритм Хопкрофта-Карпа}

\begin{code}
void dfs(int v):
	for (x `\color{black}{$\in$}` N(v)): // `$x$ -- сосед во второй доле`
		if (used2[x]++ == 0) // `проверили, что в $x$ попадаем впервые`
			if (pair2[x] == -1 || (dist[pair2[x]] == dist[v]+1 && dfs(pair2[x])):
				pair1[v] = x, pair2[x] = v 
				return 1
	return 0
while (bfs `\color{black}{нашёл путь свободной в свободную}`): // `цикл по фазам`
	used2 <-- 0 // `пометки для вершин второй доли`
	for (v `\color{black}{$\in$}` A): // `вершины первой доли`
		if (pair1[v] == -1): // `вершина свободна`
			dfs(v)
\end{code}
$\forall$ вершины $v$ второй доли в $G_f$ из $v$ исходит не более одного ребра.\\
Для свободной вершины это ребро в сток $t$, для несвободной в её пару в первой доле.

Значит, заходить в $v$ dfs-ам одной фазы Диница имеет смысл только один раз.

\down
Давайте вместо ``удаления рёбер'' помечать вершины второй доли. 
Посмотрим на происходящее, как на поиск ДЧП для паросочетания. Поймём, что сток с истоком нам особо не нужны...

\pagebreak
\vspace*{-1.5em}
\Subsection{Теоремы Карзанова}

Определим пропускную способность вершины: 
\begin{smallformula}
$$c[v] = \min(c_{in}[v],c_{out}[v]), \text{где }c_{in}[v] = \sum_{e \in in[v]}c_e, c_{out}[v] = \sum_{e \in out[v]}c_e$$
\end{smallformula}
\begin{Thm}\label{thm@karzanov1}
Число фаз алгоритма Диницы не больше $2\sqrt{C}$, где $С = \sum_v c[v]$.
\end{Thm}
\begin{proof}
Заметим, что $\forall$ потока $f$ и вершины $v \not= s, t$ величины $c_in[v], c_out[v], c[v]$ равны значениям в исходном графе.
Запустим первые $\sqrt{C}$ фаз, получим поток $f_0$, пусть $|f^{*}| = \max$, рассмотрим декомпозицию $f^{*} - f_0$. 
Она состоит из $k = |f^{*}| - |f_0|$ единичных путей длины хотя бы $\sqrt{C}$ (не считая $s$ и $t$). Обозначим $\alpha_v$ -- сколько путей проходят через $v$.
Тогда: 

\begin{center}
$k \sqrt{C} \le \sum_{v \not= s, t} \alpha_v \le \sum_{v \not= s, t} c[v] = C \SO k \le \sqrt{C}$
\end{center}

Получили, что число фаз $\le \sqrt{C} + k \le 2\sqrt{C}$.
\end{proof}
\begin{Cons}Из теоремы следует время работы Хопкрофта-Карпа.\end{Cons}

\begin{Prop}В единичных сетях $C \le E \SO$ алгоритм Диница работает за $\O(E^{3/2})$.\end{Prop}

\begin{Thm}\label{thm@karzanov2}
Число фаз алгоритма Диницы не больше $2U^{1/2}V^{2/3}$, где $U = \max_e c_e$.
\end{Thm}
\begin{proof}
Запустим первые $k$ фаз (оптимальное $k$ выберем позже), на $(k{+}1)$-й получим слоистую сеть из $\ge k{+}1$ слоёв.
Обозначим размеры слоёв $a_0, a_1, a_2, \dots, a_k$.\\
Тогда величина $\min$ разреза не более $\min_{i=1..k} (a_{i-1}a_iU)$. \\
Максимум такого минимума достигается при $a_1 = a_2 = \dots a_k = \mfrac{V}{k}$.\\
Получили разрез размера $U(\mfrac{V}{k})^2 \SO$ осталось не более чем столько фаз $\SO$

\begin{center}
всего фаз не более $f(k) = k + U(\mfrac{V}{k})^2$. $\ \ k \uparrow, U(\mfrac{V}{k})^2 \downarrow$.
\end{center}

Асимптотический минимум $f$ достигается при $k = U(\mfrac{V}{k})^2 \SO k^3 = UV^2$, число фаз $\le 2(UV^2)^{1/3}$.
\end{proof}

\up\up\up
\Subsection{Диниц с link-cut tree}

Улучшим время одной фазы алгоритмы Диница с $\O(VE)$ до $\O(E \log V)$.

Построим остовное дерево с корнем в $t$ по входящим не насыщенным рёбрам.

\down
Теперь $E$ раз пускаем поток, по пути дерева $s \leadsto t$ и перестраиваем дерево.\\
Для этого находим на пути $s \leadsto t$ любое одно насытившееся ребро $a \to b$, разрезаем его, и для вершины $a$
добавляем в дерево следующее ребро из $out[a]$. Цикла появиться не может: рёбра идут вперёд по слоям.
Зато у $a$ могли просто кончиться рёбра, тогда $a$ объявляем тупиковой веткой развития, и рекурсивно разрезаем ребро, входящее в $a$.

\down
Заметим, что {\it link-cut-tree} со {\it splay-tree} умеет делать все описанные операции за $\O(\log V)$:
\up
\begin{MyItemize}[0pt]
	\item Поиск минимума и позиции минимума величины $c_e - f_e$ на пути.
	\item Уменьшение величины $c_e - f_e$ на пути.
	\item Разрезание ребра (cut), проведение нового ребра (link).
\end{MyItemize}

\up
Один cut может рекурсивно удалить много рёбер, сильно перестроить дерево.
Несмотря на это каждое ребро удалится не более одного раза $\SO$ суммарное время всех cut -- $\O(E \log V)$.

\pagebreak
\vspace*{-1.5em}
\Subsection{Глобальный разрез}

\THEE{Задача:} найти разбиение $V = A \sqcup B \colon A, B \not= \EMPTY, C(A, B) \to \min$.

Простейшее решение: переберём $s$, $t$ и найдём разрез между ними. Конечно, можно взять $s = 1$.

Время работы $\O(V \cdot Flow)$.

На практике покажем, что на единичных сетях эта идея работает уже за $\O(E^2)$.

\Subsubsection{Алгоритм Штор-Вагнера}

Выберем $a_1 = 1$. Пусть $A_i = \{a_1, a_2, \dots, a_i\}$.
Определим $a_{i+1} = v \in V \setminus A_i \colon C(A_i, \{v\}) = \max$.
\begin{Prop}
Минимальный разрез между $a_n$ и $a_{n-1}$ -- $S = \{a_n\}, T = V \setminus S$, где $n = |V|$.
\end{Prop}
\begin{proof}
Можно прочесть на \href{http://e-maxx.ru/algo/stoer_wagner_mincut#3}{e-maxx}.
\end{proof}
\up
\THEE{Алгоритм:} или $a_n$ и $a_{n-1}$ по разные стороны оптимального глобального разреза,
и ответ равен $C(\{a_n\}, V \setminus \{a_n\})$, или $a_n$ и $a_{n-1}$ можно стянуть в одну вершину.

\THEE{Время работы:} $V$ фаз, каждая за $\O(Dijkstra) \SO \O(V(E + V \log V))$.

\Subsubsection{Алгоритм Каргера-Штейна}

Пусть $c_e \equiv 1$. Минимальную степень обозначим $k$.\\
$\exists v \colon deg_v = k \SO C(\{v\}, V \setminus \{v\}) = k \SO$ в $\min$ разрезе не более $k$ рёбер.
$E = \mfrac{1}{2} \sum deg_v \ge \mfrac{1}{2}kV$.\\
Возьмём случайное ребро $e$, вероятность того, что оно попало в разрез $Pr[e \in cut] \le \mfrac{k}{E} = \mfrac{2}{V}$.

\THE{Алгоритм Каргера.}

Пока в графе $>2$ вершин, выбираем случайное ребро, не являющееся петлёй, стягиваем его концы в одну вершину.
В конце $V' = \{A, B\}$, объявляем минимальным разрезом $V = A \sqcup B$.

\THEE{Время работы:} $T(V) = V + T(V-1) = \Theta(V^2)$. \fix{Здесь $V$ -- время стягивания двух вершин.}

\THEE{Вероятность успеха:} ни разу не ошиблись с 
$Pr \ge \mfrac{{V-2}}{V} \cdot \mfrac{{V-3}}{V-1} \cdot \mfrac{{V-4}}{{V-2}} \cdot \ldots \cdot \mfrac{1}{{3}} = \mfrac{2 \cdot 1}{V \cdot (V-1)} \ge \mfrac{2}{V^2}$.

Чтобы алгоритм имел константную вероятность ошибки, достаточно запустить его $V^2 \SO$ \\
получили \t{RP}-алгоритм за $\O(V^4)$.

\THE{Алгоритм Каргера-Штейна.}

В оценке $\mfrac{{V-3}}{V-1} \cdot \mfrac{{V-4}}{{V-2}} \cdot \ldots \cdot \mfrac{1}{{3}}$ 
большинство первых сомножителей близки к $1$. Последние \\
сомножители -- $\mfrac{2}{4}, \mfrac{1}{3}$ напротив весьма малы
$\SO$ остановимся, когда в графе останется $\mfrac{V}{\sqrt{2}}$ вершин. \\
Вероятность ни разу не ошибиться при этом будет
$\mfrac{V/\sqrt{2}(V/\sqrt{2}-1)}{V(V-1)} \approx \mfrac{1}{2}$. \\
\fix{Время, потраченное на $(V - V/\sqrt{2})$ сжатий -- $\Theta(V^2)$.}

\down
После этого сделаем два рекурсивных вызова от получившегося графа с $V/\sqrt{2}$ вершинами.
Алгоритм рандомизированный $\SO$ ветки рекурсии могут дать разные разрезы $\SO$ вернём минимальный из полученных.

\THEE{Время работы:} $T(V) = V^2 + 2T(\mfrac{V}{\sqrt{2}}) = V^2 + 2(\mfrac{V}{ \sqrt{2}})^2 + 4T(\mfrac{V}{\sqrt{2}^2}) = \dots = V^2 \log V$.

\THEE{Вероятность ошибки.} Ищем $p(V)$, вероятность успеха на графе из $V$. \\
Обозначим $p(V) = q_k, p(V/\sqrt{2}) = q_{k-1}, \dots, \SO $\\
$q_i = \mfrac{1}{2} + \mfrac{1}{2}(1 - (1{-}q_{i-1})^2) = q_{i-1} - \mfrac{1}{2}q_{i-1}^2 \SO q_i{-}q_{i-1} = -q_{i-1}^2$.
Левая часть похожа на производную $\SO$ решим диффур $q'(x) = -q(x)^2 \EQ \mfrac{-q'(x)}{q(x)^2} = 1 \EQ q(x)^{-1} = x + C \SO q_k = \Theta(\mfrac{1}{k}) \SO p(V) = \Theta(\mfrac{1}{\log V})$.

\down\down
Короткая и быстрая реализация получается через \t{random\_shuffle} исходных рёбер.\\
Подробнее в разборе \href{http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/170929.pdf}{практики}.