\begingroup
\allowdisplaybreaks

\Section{Потоки}{5 апреля}{Веселов Иван}

\Subsection{Основные определения}

\begin{Def}
  \underline{Сеть}. Пусть дан ориентированный граф $G = (V, E)$ без кратных ребер и петель с выделенными в нем вершинами $s, t \in V$.
  Вершины $s$ и $t$ называются истоком и стоком соответственно. Пусть также введена функция
  $c : V \times V \rightarrow \mathbb{R}_{\geq 0}$, которая называется пропускной способностью ребра, причем если $(u, v) \notin E$, то $c(u, v) = 0$.
  В таком случае четверка $(G, s, t, c)$ называется \textbf{сетью}.
\end{Def}

\begin{Def}
  \underline{Инцидентные ребра}. Пусть дан ориентированный граф $G$. Для произвольной вершины $v \in V$ обозначим за
  $In\ v = \{e \in E : \exists u \in V, e = (u, v)\}$ -- множество ребер, входящих в вершину $v$. Аналогично определим
  $Out\ v = \{e \in E : \exists u \in V, e = (v, u)\}$ -- множество ребер, исходящих из вершины $v$.
\end{Def}

\begin{Def}
  \underline{Поток в сети} (по Асанову). Пусть дана сеть $(G, s, t, c)$. Потоком в этой сети называется функция
  $f : E \rightarrow \mathbb{R}_{\geq 0}$, которая удовлетворяет следующим условиям:
  \begin{itemize}
    \item[1.] $\forall e \in E: f(e) \leq c(e)$. То есть по ребру не может течь больше, чем это ребро способно пропустить.
    \item[2.] $\forall v \in V \setminus \{s, t\}: \sum\limits_{e \in In\ v}{f(e)} = \sum\limits_{e \in Out\ v}{f(e)}$.
    То есть сколько в вершину, отличную от истока и стока, затекло, столько из нее и вытекло.
  \end{itemize}
\end{Def}

\begin{Lm}\label{Lm:flow_in_out}
  $\sum\limits_{e \in Out\ s}{f(e)} - \sum\limits_{e \in In\ s}{f(e)} = \sum\limits_{e \in In\ t}{f(e)} - \sum\limits_{e \in Out\ t}{f(e)}$.
  То есть сколько потока вытекло из стока и не затекло обратно, столько и затекло в сток и не вытекло обратно.
  \begin{proof}
    \begin{align*}
      \sum\limits_{v \in V}{\sum\limits_{e \in In\ v}{f(e)}} = \sum\limits_{e \in E}{f(e)},\\
      \sum\limits_{v \in V}{\sum\limits_{e \in Out\ v}{f(e)}} = \sum\limits_{e \in E}{f(e)} \Rightarrow\\
      \Rightarrow \sum\limits_{v \in V}{\sum\limits_{e \in In\ v}{f(e)}} = \sum\limits_{v \in V}{\sum\limits_{e \in Out\ v}{f(e)}} \Leftrightarrow\\
      \Leftrightarrow \sum\limits_{v \in V}{\bigg[\sum\limits_{e \in In\ v}{f(e)} - \sum\limits_{e \in Out\ v}{f(e)}\bigg]} = 0 \Leftrightarrow\\
      \Leftrightarrow \bigg[\sum\limits_{e \in In\ s}{f(e)} - \sum\limits_{e \in Out\ s}{f(e)}\bigg] + \bigg[\sum\limits_{e \in In\ t}{f(e)} - \sum\limits_{e \in Out\ t}{f(e)}\bigg] + \\
      + \sum\limits_{v \in V \setminus \{s, t\}}{\bigg[\sum\limits_{e \in In\ v}{f(e)} - \sum\limits_{e \in Out\ v}{f(e)}\bigg]} = 0 \Leftrightarrow \text{(По (2) свойству потока)}\\
      \Leftrightarrow \sum\limits_{e \in In\ s}{f(e)} - \sum\limits_{e \in Out\ s}{f(e)} + \sum\limits_{e \in In\ t}{f(e)} - \sum\limits_{e \in Out\ t}{f(e)} = 0 \Leftrightarrow\\
      \Leftrightarrow \sum\limits_{e \in Out\ s}{f(e)} - \sum\limits_{e \in In\ s}{f(e)} = \sum\limits_{e \in In\ t}{f(e)} - \sum\limits_{e \in Out\ t}{f(e)}
    \end{align*}
  \end{proof}
\end{Lm}

\begin{Rem}
  Если $deg_{in}\ s = deg_{out}\ t = 0$, то $\sum\limits_{e \in Out\ s}{f(e)} = \sum\limits_{e \in In\ t}{f(e)}$.
  То есть сколько потока из истока вытекло, столько и затекло в сток.
  \begin{proof}
    В таком случае просто $\sum\limits_{e \in In\ s}{f(e)} = \sum\limits_{e \in Out\ t}{f(e)} = 0$, так как таких ребер просто нет.
  \end{proof}
\end{Rem}

\begin{Def}
  \underline{Величина потока}. Величиной потока $f$ в сети $(G, s, t, c)$ называется $\sum\limits_{e \in Out\ s}{f(e)} - \sum\limits_{e \in In\ s}{f(e)}$,
  то есть количество потока, которое вытекает из истока и не затекает обратно. Обозначается $|f|$. Согласно лемме (\autoref{Lm:flow_in_out}) $|f| = \sum\limits_{e \in In\ t}{f(e)} - \sum\limits_{e \in Out\ t}{f(e)}$.
\end{Def}

\begin{Remark}
  Таким образом можно представлять поток как некое вещество, вытекающее из истока в некотором количестве, как-то хаотично протекающее через промежуточные
  узлы, не задерживаясь в них, и в конечном итоге стекающее в сток. Но на самом деле в потоке еще могут присутствовать и циркуляции -- части
  этого вещества, которые циркулируют по некоторым циклам.
\end{Remark}

\begin{Def}
  \underline{Циркуляция}. Циркуляцией называется такой поток $f$, что $|f| = 0$, но $\exists e \in E: f(e) > 0$.
\end{Def}

\begin{Remark}
  На практике с определением потока по Асанову оказывается трудно работать, поэтому вводится другое определение потока.
\end{Remark}

\begin{Def}
  \underline{Поток в сети}. Пусть дана сеть $(G, s, t, c)$, в которой для каждого ребра \textbf{существует обратное}.
  Потоком в этой сети называется функция $f : V \times V \rightarrow \mathbb{R}$, которая удовлетворяет следующим условиям:
  \begin{itemize}
    \item[1.] $\forall u, v \in V: f(u, v) = -f(v, u)$. Антисимметричность.
    \item[2.] $\forall u, v \in V: f(u, v) \leq c(u, v)$. То есть по ребру не может течь больше, чем это ребро способно пропустить.
    \item[3.] $\forall u \in V \setminus \{s, t\}: \sum\limits_{v \in V}{f(u, v)} = 0$. Это свойство сходно со вторым свойством потоков по Асанову.
  \end{itemize}
\end{Def}

\begin{Remark}
  Если для некоторых вершин $u, v \in V: f(u, v) > 0$, то поток данной величины течет от вершины $u$ к вершине $v$. Благодаря антисимметричности
  $f(v, u) < 0$ и это следует воспринимать так же, как отрицательную прибыль, то есть убыток. По ребру $(v, u)$ как бы притекает отрицательное
  количество потока $f(v, u) = -f(u, v)$, иными словами утекает $-f(v, u) = f(u, v)$.\\
  Если для некоторых вершин $u, v \in V: f(u, v) = 0$, то $f(v, u) = -f(u, v) = 0$.\\
  Таким образом между двумя вершинами $u, v \in V$ поток либо течет в одну сторону, либо не течет вообще. Причем если $f(u, v) > 0$, то
  по второму свойству потока $c(u, v) \geq f(u, v) > 0 \Rightarrow (u, v) \in E$. То есть если поток течет от $u$ к $v$, то он течет по
  существующему ребру.\\
  Данные рассуждения подводят к следующей теореме.
\end{Remark}

\begin{Thm}\label{Thm:flows_equivalence}
  Пусть дана сеть $(G, s, t, c)$ и поток $f$ (по новому определению) в ней. Тогда $f' = \max{\{0, f\big|_{E}\}}$ является потоком по Асанову.
  \begin{proof}
    Образы $f'$ неотрицательны по определению.\\
    Первое свойство:
    \begin{align*}
      \forall e \in E: f'(e) = \max{\{0, f(e)\}} \leq c(e)
    \end{align*}
    Второе свойство:
    \begin{align*}
      \forall u \in V \setminus \{s, t\}: \sum\limits_{e \in Out\ u}{f'(e)} - \sum\limits_{e \in In\ u}{f'(e)} =\\
      = \sum\limits_{e \in Out\ u}{\max{\{0, f(e)\}}} + \sum\limits_{e \in In\ u}{-\max{\{0, f(e)\}}} =\\
      = \sum\limits_{e \in Out\ u}{\max{\{0, f(e)\}}} + \sum\limits_{e \in In\ u}{\min{\{0, -f(e)\}}} = \text{(для оставшихся вершин значение $0$)}\\
      = \sum\limits_{v \in V}{\max{\{0, f(u, v)\}}} + \sum\limits_{v \in V}{\min{\{0, -f(v, u)\}}} =\\
      = \sum\limits_{v \in V}{\max{\{0, f(u, v)\}}} + \sum\limits_{v \in V}{\min{\{0, f(u, v)\}}} =\\
      = \sum\limits_{v \in V}{\bigg[\max{\{0, f(u, v)\}} + \min{\{0, f(u, v)\}}\bigg]} =\\
      = \sum\limits_{v \in V}{f(u, v)} = 0 \text{(по третьему свойству потока)}
    \end{align*}
  \end{proof}
\end{Thm}

\begin{Remark}
  Как и в потоке по Асанову вводится величина потока $|f| = \sum\limits_{u \in V}{f(s, u)}$, которая совпадает с $\sum\limits_{u \in V}{f(u, t)}$,
  а также $|f| = |\max{\{0, f\big|_{E}\}}|$. Доказательство этих фактов просто комбинирует лемму (\autoref{Lm:flow_in_out})
  и теорему (\autoref{Thm:flows_equivalence}).
\end{Remark}

\begin{Remark}
  В дальнейшем будут рассматриваться исключительно потоки по новому определению, так как с ними удобней работать.
\end{Remark}

\begin{Def}
  \underline{Остаточная сеть}. Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней. Остаточной сетью называется новая сеть
  $G_{f} = (G, s, t, c_{f})$, где $c_{f} = c - f$ и назывется остаточной пропускной способностью.\\
  По второму свойству потока $\forall u, v \in V: f(u, v) \leq c(u, v) \Rightarrow c(u, v) - f(u, v) \geq 0$. Таким образом в остаточной сети
  пропускные способности неотрицательные.
\end{Def}

\begin{Lm}\label{Lm:flow_in_rem}
  Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней, а также поток $f'$ в $G_{f}$. Тогда $F = f + f'$ поток в исходной сети, причем $|F| = |f| + |f'|$.
  \begin{proof}
    Первое свойство:
    \begin{align*}
      \forall u, v \in V: F(u, v) = f(u, v) + f'(u, v) = -f(v, u) - f'(v, u) = -(f(v, u) + f'(v, u)) = -F(v, u)
    \end{align*}
    Второе свойство:
    \begin{align*}
      \forall u, v \in V: F(u, v) = f(u, v) + f'(u, v) \leq f(u, v) + c(u, v) - f(u, v) = c(u, v)
    \end{align*}
    Третье свойство:
    \begin{align*}
      \forall u \in V \setminus \{s, t\}: \sum\limits_{v \in V}{F(u, v)} = \sum\limits_{v \in V}{\bigg[f(u, v) + f'(u, v)\bigg]} =
      \sum\limits_{v \in V}{f(u, v)} + \sum\limits_{v \in V}{f'(u, v)} = 0
    \end{align*}
    Величина потока:
    \begin{align*}
      |F| = \sum\limits_{u \in V}{F(s, u)} = \sum\limits_{u \in V}{\bigg[f(s, u) + f'(s, u)\bigg]} =
      \sum\limits_{u \in V}{f(s, u)} + \sum\limits_{u \in V}{f'(s, u)} = |f| + |f'|
    \end{align*}
  \end{proof}
\end{Lm}

\begin{Remark}
  На практике остаточная сеть хранится в виде пары чисел: пропускной способности ребра и количества потока, протекающего по этому
  ребру.
\end{Remark}

\begin{Def}
\underline{Разрез в сети}. Пусть дана сеть $(G, s, t, c)$.
$\langle S, T \rangle$ разрезом в сети называется два множества $S, T \subset V$, такие что:
  \begin{itemize}
    \item[1.] $S \cap T = \varnothing$
    \item[2.] $S \cup T = V$
    \item[3.] $s \in S, t \in T$
  \end{itemize}
  
  То есть разрез -- это разбиение вершин графа на две части таким образом, что исток и сток попадают в разные части.
\end{Def}

\begin{Def}
  \underline{Величина разреза}. Величиной разреза называется $|\langle S, T \rangle| = \sum\limits_{u \in S, v \in T}{c(u, v)}$. То есть
  суммарная пропускная способность ребер, проходящих из $S$ в $T$.
\end{Def}

\begin{Remark}
  Величина разреза считается для исходной сети, а не для остаточной.
\end{Remark}

\Subsection{Задача о максимальном потоке, теорема Форда-Фалкерсона}\\
Ясно, что величина потока ограничена сверху суммарной пропускной способностью ребер, исходящих из истока. Встает закономерный вопрос:
существует ли максимальный поток среди всевозможных, и если да, то как его отыскать?

\begin{Def}
  \underline{Дополняющий путь.} Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней. Дополняющим путем называется такой путь
  $p$ из $s$ в $t$, что $\forall e \in p: c_{f}(e) > 0$.
\end{Def}

\begin{Lm}\label{Lm:inc_path}
  Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней. Если существует дополняющий путь, то $f$ не максимален.
  \begin{proof}
    Пусть $p$ простой дополняющий путь (если есть какой-то, то его можно сжать до простого). Рассмотрим поток $f'$ в $G_{f}$,
    который пропускает по каждому ребру из $p$ $\min\limits_{e \in p}{\{c_{f}(e)\}} > 0$ единиц потока.
    Тогда по лемме (\autoref{Lm:flow_in_rem}) $f + f'$ -- поток в исходной сети, причем $|f + f'| = |f| + |f'|$, но
    $|f'| = \sum\limits_{u \in V}{f'(s, u)} = f'(s, p_{1}) = f'(p_{0}, p_{1}) = \min\limits_{e \in p}{\{c_{f}(e)\}} > 0$, где $p_{i}$ --
    $i$-ая вершина в пути $p$. Таким образом $|f| + |f'| > |f|$, значит поток $f$ не максимальный.
  \end{proof}
\end{Lm}

\begin{Lm}\label{Lm:flow_trough_cut}
  Пусть дана сеть $(G, s, t, c)$ и разрез $\langle S, T \rangle$ в ней. Тогда $|f| = \sum\limits_{u \in S, v \in T}{f(u, v)}$. То есть поток,
  протекающий через разрез, равен по величине потоку в сети.
  \begin{proof}
    \begin{align*}
      |f| = \sum\limits_{u \in V}{f(s, u)} = \text{(по (3) свойству потока)}\\
      = \sum\limits_{v \in V}{f(s, v)} + \sum\limits_{u \in S \setminus \{s\}}{\sum\limits_{v \in V}{f(u, v)}} =\\
      = \sum\limits_{u \in S}{\sum\limits_{v \in V}{f(u, v)}} =\\
      = \sum\limits_{u \in S}{\bigg[\sum\limits_{v \in S}{f(u, v)} + \sum\limits_{v \in T}{f(u, v)}\bigg]} =\\
      = \sum\limits_{u \in S}{\sum\limits_{v \in S}{f(u, v)}} + \sum\limits_{u \in S}{\sum\limits_{v \in T}{f(u, v)}} =\\ \text{(каждое ребро в $S$ посчиталось вместе с обратным, но по антисимметричности это $0$)}\\
      = \sum\limits_{u \in S}{\sum\limits_{v \in T}{f(u, v)}} =\\
      = \sum\limits_{u \in S, v \in T}{f(u, v)}
    \end{align*}
  \end{proof}
\end{Lm}

\begin{Lm}\label{Lm:flow_cut_ineq}
  Пусть дана сеть $(G, s, t, c)$. $\forall$ разреза $\langle S, T \rangle$ и потока $f: |f| \leq |\langle S, T \rangle|$.
  \begin{proof}
    \begin{align*}
      |f| =\text{(По лемме (\autoref{Lm:flow_trough_cut}))}\\
      = \sum\limits_{u \in S, v \in T}{f(u, v)} \leq \text{(по (2) свойству потока)}\\
      \leq \sum\limits_{u \in S, v \in T}{c(u, v)} =\\
      = |\langle S, T \rangle|
    \end{align*}
  \end{proof}
\end{Lm}

\begin{Lm}\label{Lm:inc_path_min_cut}
  Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней. Если дополняющих путей не существует, то
  $\exists \langle S, T \rangle: |f| = |\langle S, T \rangle|$.
  \begin{proof}
    Построим этот разрез конструктивно. Возьмем в качестве множества $S$ множество всех вершин, которые достижимы из $s$
    по ребрам, для которых $c_{f} > 0$. Тогда $T = V \setminus S$, и $t \in T$, так как иначе это бы означало, что существует
    дополняющий путь. $\forall u \in S, v \in T: f(u, v) = c(u, v)$, так как иначе было бы $f(u, v) < c(u, v) \Rightarrow
    c_{f}(u, v) = c(u, v) - f(u, v) > 0$ и $v$ должна была бы попасть в $S$. Но по лемме (\autoref{Lm:flow_trough_cut}):
    $|f| = \sum\limits_{u \in S, v \in T}{f(u, v)} = \sum\limits_{u \in S, v \in T}{c(u, v)} = |\langle S, T \rangle|$.
  \end{proof}
\end{Lm}

\begin{Rem}
  Разрез $\langle S, T \rangle$ из леммы является минимальным разрезом.
  \begin{proof}
    От противного через лемму (\autoref{Lm:flow_cut_ineq}).
  \end{proof}
\end{Rem}

\begin{Thm}\label{Thm:Ford-Fulkerson}
  (Форд-Фалкерсон). Пусть дана сеть $(G, s, t, c)$ с потоком $f$ в ней. Тогда следующие три утверждения эквивалентны:
    \begin{itemize}
      \item[1.] Поток $|f|$ максимален.
      \item[2.] Дополняющие пути отсутствуют.
      \item[3.] $\exists \langle S, T \rangle: |f| = |\langle S, T \rangle|$.
    \end{itemize}
    \begin{proof}
      $(1) \Rightarrow (2):$\\
      От противного по лемме (\autoref{Lm:inc_path}).\\
      $(2) \Rightarrow (3):$\\
      Лемма (\autoref{Lm:inc_path_min_cut}).\\
      $(3) \Rightarrow (1):$\\
      От противного по лемме (\autoref{Lm:flow_cut_ineq}).
    \end{proof}
\end{Thm}

\begin{Remark}
  Теорема Форда-Фалкерсона не отвечает на вопрос о существовании максимального потока в произвольной сети.
\end{Remark}

\Subsection{Алгоритм Форда-Фалкерсона}\\
\begin{Def}
  \underline{Целочисленная сеть}. Сеть $(G, s, t, c)$ называется целочисленной, если $Im\ c \subset \mathbb{Z}$.
\end{Def}

\begin{Def}
  \underline{Целочисленный поток}. Поток $f$ называется целочисленным, если $Im\ f \subset \mathbb{Z}$.
\end{Def}

\begin{Thm}
  (Алгоритм Форда-Фалкерсона). В целочисленной сети $(G, s, t, c)$ существует максимальный поток, и причем целочисленный.
  \begin{proof}
    Конструктивное доказательство. Пусть в произвольный момент времени набран целочисленный поток $f_{k}$ размера $k$. Если
    не существует дополняющих путей, то по теореме (\autoref{Thm:Ford-Fulkerson}) поток $f_{k}$ максимальный. Иначе остаточная
    сеть $G_{f_{k}}$ целочисленная и в ней существует дополняющий путь, по которому можно пропустить единицу потока. Сделав это
    перейдем к потоку $f_{k + 1}$ размера $k + 1$. Изначально поток нулевой, а увеличивать поток таким образом получится не более
    $\sum\limits_{u \in V}{c(s, u)}$ раз, что означает, что в какой-то момент не останется дополняющих путей и поток будет
    максимальным.
  \end{proof}
\end{Thm}

\begin{Remark}
  Если искать путь с помощью обхода в глубину, то алгоритм работает за $\mathcal{O}(E \cdot |f|)$.
\end{Remark}

\begin{Remark}
  С практической точки зрения алгоритм можно немного ускорить, если пропускать по пути не $1$ потока, а минимум среди $c_{f}$ на пути.
\end{Remark}

\Subsection{Существование максимального потока в произвольной сети. Алгоритм Эдмондса-Карпа}\\
\begin{Algo}
  (Эдмондс-Карп). Алгоритм ищет максимальный поток в произвольной сети $(G, s, t, c)$.
  В произвольный момент времени набран некоторый поток $f$. Если не существует дополняющих
  путей, то по теореме (\autoref{Thm:Ford-Fulkerson}) поток $f$ максимальный. Иначе найдем дополняющий путь $p$ минимальной
  длины (в ребрах) и пропустим по нему $\min\limits_{e \in p}{\{c_{f}(e)\}}$ единиц потока.
\end{Algo}

Все последующие рассуждения этого раздела неразрывно связаны с алгоритмом Эдмонса-Карпа и нацелены на доказательство его конечности.

\begin{Def}
  \underline{Расстояние до вершины}. Обозначим за $d_{i}(v)$ расстояние в ребрах от $s$ до вершины $v \in V$ в остаточной сети $G_{f_{i}}$ (то
  есть по ребрам для которых $c_{f_{i}} = 0$ ходить нельзя), где $f_{i}$ поток, набранный алгоритмом Эдмондса-Карпа после добавления $i$
  дополняющих путей.
\end{Def}

\begin{Lm}\label{Lm:distance_inc}
  Пусть $v \in V$, тогда $d_{i}(v) \nearrow$.
  \begin{proof}
    Зафиксируем момент времени $i$ и докажем, что $\forall v \in V: d_{i + 1}(v) \geq d_{i}(v)$.\\
    Пусть $\exists v \in V: d_{i + 1}(v) < d_{i}(v)$ (теоретически $d_{i}(v)$ может равняться $+\infty$, что означает, что вершина $v$ была недостижима
    из $s$), среди таких возьмем $v$ с минимальным $d_{i + 1}$. $v \neq s$, так как
    $\forall i: d_{i}(s) = 0$. Тогда обозначим за $u$ вершину на кратчайшем пути от $s$ до $v$ в $G_{f_{i + 1}}$, предшествующую $v$. В таком случае
    $d_{i + 1}(v) = d_{i + 1}(u) + 1 \Rightarrow d_{i + 1}(u) < d_{i + 1}(v) \Rightarrow \text{(по предположению)} d_{i + 1}(u) \geq d_{i}(u)\ \text{(*)}$.
    Возможно две ситуации:
    \begin{itemize}
      \item[1.] $c_{f_{i}} > 0$, то есть ребро $(u, v)$ присутствовало до добавления дополняющего пути. Тогда
      $d_{i + 1}(v) = d_{i + 1}(u) + 1 \geq \text{(согласно (*))} d_{i}(u) + 1 \geq \text{(неравенство треугольника, так как ребро было)} d_{i}(v)$,
      что противоречит предположению.
      \item[2.] $c_{f_{i}} = 0$, то есть ребро $(u, v)$ появилось после добавления дополняющего пути. Но тогда
      $c(u, v) - f_{i}(u, v) = 0, c(u, v) - f_{i + 1}(u, v) > 0 \Rightarrow f_{i}(u, v) - f_{i + 1}(u, v) > 0 \Rightarrow
      f_{i + 1}(v, u) - f_{i}(v, u) > 0$, но поток $f_{i + 1}$ получился из $f_{i}$ добавлением дополняющего пути, а значит разность и есть
      дополняющий путь. Тогда неравенство означает, что ребро $(v, u)$ принадлежит дополняющему пути (что сразу исключает возможность того, что
      $d_{i}(v) = +\infty$), а так как он кратчайший, то
      $d_{i}(u) = d_{i}(v) + 1 \Rightarrow d_{i}(v) = d_{i}(u) - 1 \leq \text{(согласно (*))} d_{i + 1}(u) - 1 = d_{i + 1}(v) - 2 < d_{i + 1}(v)$, что противоречит
      предположению.
    \end{itemize}
  \end{proof}
\end{Lm}

\begin{Def}
  \underline{Насыщение ребра}. Ребро $(u, v)$ насыщается после добавления $(i + 1)$-ого дополняющего пути, если $c_{f_{i}} > 0$, а
  $c_{f_{i + 1}} = 0$.
\end{Def}

\begin{Lm}\label{Lm:EC-filled-edge}
  В течении работы алгоритма $\forall$ ребро $(u, v)$ насытится не более $\frac{V}{2} + 1$ раз.
  \begin{proof}
    Рассмотрим некоторый момент $a$ насыщения произвольного ребра $(u, v): c_{f_{a}}(u, v) > 0, c_{f_{a + 1}}(u, v) = 0$ и другой
    момент $c$ насыщения этого же ребра $c_{f_{c}}(u, v) > 0, c_{f_{c + 1}}(u, v) = 0$, так как $c_{f_{a + 1}}(u, v) = 0$, а
    $c_{f_{c}}(u, v) > 0$, то $\exists b \in (a, c): c_{f_{b}}(u, v) = 0, c_{f_{b + 1}}(u, v) > 0$. По рассуждениям, аналогичными со вторым случаем
    в лемме (\autoref{Lm:distance_inc}), ребро $(v, u)$ принадлежит $(b + 1)$-ому дополняющему пути, а значит
    $d_{b + 1}(u) = d_{b + 1}(v) + 1 \Rightarrow d_{a + 1}(v) \leq d_{b + 1}(v) = d_{b + 1}(u) - 1 \leq d_{c}(u) - 1 = d_{c}(v) - 2$, оба неравенства верны
    по лемме (\autoref{Lm:distance_inc}). Таким образом $d_{a + 1}(v) + 2 \leq d_{c}(v)$, то есть от одного насыщения до следующего расстояние до
    конца ребра увеличится хотя бы на $2$. Так как это расстояние не может превышать $V$, то суммарное количество насыщений не более $\frac{V}{2} + 1$.
  \end{proof}
\end{Lm}

\begin{Thm}
  Алгоритм Эдмондса-Карпа работает за конечное время.
  \begin{proof}
    Так как за добавление дополняющего пути хотя бы одно ребро насыщается (то, на котором достигается минимум среди остаточных пропускных способностей),
    то по лемме (\autoref{Lm:EC-filled-edge}) через $E(\frac{V}{2} + 1)$ таких добавлений ни одно ребро нельзя будет насытить, что означает отсутствие
    дополняющих путей.
  \end{proof}
\end{Thm}

\begin{Remark}
  Если искать кратчайший дополняющий путь с помощью обхода в ширину, то алгоритм будет работать за $\mathcal{O}(VE^{2})$
\end{Remark}

\begin{Remark}
  В целочисленной сети алгоритм найдет целочисленный поток.
\end{Remark}

\begin{Thm}
  В произвольной сети $(G, s, t, c)$ существует максимальный поток.
  \begin{proof}
    Алгоритм Эдмондса-Карпа является конструктивным доказательством этого факта.
  \end{proof}
\end{Thm}

\Subsection{Декомпозиция потока}\\
\begin{Thm}
  Любой поток $f$ в сети $(G, s, t, c)$ можно разбить на сумму потоков $\sum\limits_{i = 1}^{n}{f_{i}}$, где $f_{i}$ либо простой путь из $s$ в $t$,
  либо цикл.
  \begin{proof}
    Конструктивное доказательство. Запустим обход из $s$ по ребрам, вдоль которых течет поток. Если обход дошел до $t$, то найден простой путь
    из $s$ в $t$, по которому можно отменить $\min\limits_{e \in p}{\{f(e)\}}$ потока. Если обход нашел цикл, то можно отменить поток по циклу.
    Когда обход заходит в очередную вершину, то если это не сток, то обход сможет пойти в следующую вершину благодаря (3) свойству потока. Так
    как каждый раз хотя бы через одно ребро перестает течь поток, то алгоритм завершится, когда из $s$ не будет ребер, по которым течет поток. К
    этому моменту в сети могла остаться циркуляция, которую можно разбить аналогичным образом, запуская обход из вершин, отличных от $s$. 
  \end{proof}
\end{Thm}

\begin{Remark}
  Алгоритм работает за $\mathcal{O}(E^{2})$.
\end{Remark}

\begin{Remark}
  $|f| = \sum\limits_{i = 1}^{n}{|f_{i}|}$.
\end{Remark}

\begin{Remark}
  Декомпозиция целочисленного потока целочисленна.
\end{Remark}

\begin{Remark}
  Время работы алгоритма можно улучшить до $\mathcal{O}(VE)$, если для каждой вершины поддерживать указатель на первое исходящее
  ребро по которому можно пройти. Тогда все обходы отработают за $\mathcal{O}(kV + E)$, где $k$ количество обходов.
\end{Remark}
\endgroup
