
\Section{Первая Теорема Карзанова.}{8 апреля}{Андрей Тонких}

\begin{Def}{Единичная сеть}

    Сеть, в которой все пропускные способности равны единице.

\end{Def}

\begin{Thm}{\emph{На единичных сетях алгоритм Диница работает за $\O(VE)$}}

\end{Thm}

\begin{proof} 
    $Time = \sum\limits_{d}(E + d \cdot K_d) \le VE + V |f| \le 2 VE$
\end{proof}

\begin{Def}
В последующих теоремах: $C := \sum\limits_{v \ne s, t} \min\{c_{in}[v], c_{out}[v]\}$
\end{Def}

\begin{Thm}{\emph{Первая теорема Карзанова.}}

    Для целочисленных пропускных способностей количество фаз $\le 2 \sqrt C$.

\end{Thm}

\begin{proof} 
    Сделаем первые $\sqrt C$ фаз, получим некоторый поток $f_1$.

    Рассмотрим $(f_{max} - f_1)$ -- поток в $G_{f_1}$, где $f_{max}$ -- какой-то максимальный поток.

    Рассмотрим декомпозицию на пути с единичным потоком и циркуляцию.

    Каждый такой путь длины больше $\sqrt C$, и для каждой промежуточной вершины
    он ``уменьшает'' потенциал $\min\{c_{in}[v], c_{out}[v]\}$ на $1$ (через вершину $v$ не может пройти больше путей).

    Таким образом каждый путь ``уменьшает'' величину 
    $C = \sum\limits_{v \ne s, t} \min\{c_{in}[v], c_{out}[v]\}$
    больше, чем на $\sqrt C$, поэтому путей меньше $\sqrt C \SO |f_{max} - f_1| < \sqrt C \SO$ алгоритм Диница в дальнейшем найдет меньше
    $\sqrt C$ путей $\SO$ будет меньше $\sqrt C$ фаз.
\end{proof}

\THE{Следствие \NO{1}:} На единичных сетях алгоитм Диница работает $\O(E \sqrt C)$.

\begin{proof}
    Каждый $dfs$ в пределах фазы ``забирает'' некоторое количество ребер, 
    а по обратным ребрам алгоритм в пределах той же фазы не пойдет 
    $\SO$ время одной фазы $= \O(E)$
\end{proof}

\THE{Следствие \NO{2}:} На единичных сетях алгоитм Диница работает $\O(E \sqrt E)$. 
\begin{proof}
    Причем $C \le 2E \SO Time = O(E \sqrt E)$
\end{proof}
