#import "@docs/bmstu:1.0.0":*
#import "@preview/tablex:0.0.8": tablex, rowspanx, colspanx, cellx
#show: student_work.with(
  caf_name: "Компьютерные системы и сети",
  faculty_name: "Информатика и системы управления",
  work_type: "домашнему заданию",  
  study_field: "09.03.01 Информатика и вычислительная техника",
  discipline_name: "Дискретная математика",
  theme: "Поток в транспортной сети. Алгоритм Форда-Фалкерсона",
  author: (group: "ИУ6-42Б", nwa: "<NAME>"),
  date: "13.05.24",
  adviser: (nwa: "<NAME>"),
  city: "Москва",
  table_of_contents: false,
)

= Задание, теоретические сведения, построение графа, определение источника и стока

== Задание 

Сеть в виде взвешенного орграфа задана матрицей Ω пропускных способностей
ориентированных ребер. При помощи алгоритма Форда – Фалкерсона определить максимальный
поток $𝜑_max$, доставляемый от источника $s = x_1$ к стоку $s = x_12$ и указать минимальный разрез, отделяющий $t$ от $s$.
Оптимизационную часть алгоритма реализовать в виде коррекции потока хотя бы на одном
увеличивающем маршруте.

Матрица пропускных способностей (вариант 19):

#align(center)[
  #tablex(
    columns: 13,
    inset: 10pt,
    align: center + horizon,
    [],[$x_1$],[$x_2$],[$x_3$],[$x_4$],[$x_5$],[$x_6$],[$x_7$],[$x_8$],[$x_9$],[$x_10$],[$x_11$],[$x_12$],
    [$x_1$], [  ],[13],[  ],[46],[26],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_2$], [  ],[  ],[  ],[  ],[  ],[  ],[20],[  ],[  ],[  ],[  ],[  ],
    [$x_3$], [  ],[  ],[  ],[  ],[  ],[12],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_4$], [  ],[  ],[  ],[  ],[  ],[21],[  ],[  ],[  ],[  ],[24],[  ],
    [$x_5$], [  ],[  ],[27],[  ],[  ],[  ],[15],[14],[  ],[  ],[  ],[  ],
    [$x_6$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[  ],
    [$x_7$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[8 ],[  ],[13],[  ],[31],
    [$x_8$], [  ],[  ],[33],[  ],[  ],[  ],[  ],[  ],[  ],[22],[  ],[  ],
    [$x_9$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[4 ],[  ],[10],[  ],[18],
    [$x_10$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[17],[50],
    [$x_11$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[22],[  ],[  ],[7],
    [$x_12$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
)]
#pagebreak()

== Теоретические сведения для решения задания


=== Теорема 1 
Если $(s, …, x_i, …, x_j, …, t)$ – путь от $s$ к $t$ и все ребра этого пути ненасыщенные, то поток на этом пути (а следовательно, и во всей сети) можно увеличить на величину $delta^∗ = min {delta (x_i, x_j)}$ по всем ребрам пути. 

При применении теоремы 1 хотя бы одно ребро становится насыщенным. При итерационном применении теорема 1 появляется ситуация, когда нет ни одного пути от источника к стоку, на котором все ребра были бы ненасыщенными. Эта ситуация говорит о полном потоке. 

=== Теорема 2

Рассмотрим маршрут из источника к стоку. Пусть на этом маршруте прямые рёбра строго ненасыщенные, а поток на обратных рёбрах строго положителен. Тогда, если $(s, …, x_i, …, x_j, …, t)$ – маршрут из $s$ к $t$, удовлетворяющий указанным условиям, то величину потока на этом маршруте (следовательно, и во всей сети) можно увеличить на величину $ε* = min{δ*, φ*}$, где $δ^*$ – минимальная остаточная пропускная способность по всем прямым ребрах маршрута, а $φ^*$ – минимальная величина потоков по всем обратным ребрам маршрута. На всех прямых ребрах маршрута потоки увеличиваются на $ε^*$, на обратных – уменьшаются на $ε^*$. Такой маршрут называется увеличивающим.

=== Теорема 3
Поток в сети достигает максимального значения тогда и только тогда, когда в сети более невозможно построить увеличивающий маршрут.

=== Теорема 4 (Теорема Форда – Фалкерсона)
Для любой сети с одним источником и одним стоком величина максимального потока $phi_max$, доставляемого от источника к стоку, равна пропускной способности минимального разреза.

=== Алгоритм Форда – Фалкерсона
- Задать начальный поток.
- Итерационно применяя теорему 1, получить полный поток.
- Итерационно применять теорему 2. При возникновении ситуации невозможности построить более увеличивающий маршрут на основании теоремы 3 достигаем максимальный поток.
- Определить разрез, по которому проходит максимальный поток. 

#pagebreak()


== Построенный граф, его источник и сток

Построим взвешенный ориентированный граф по матрице Ω пропускных способностей ориентированных ребер (рис. 1).

#img(image("1.png", width:90%), [Построенный граф])

Источником будет вершина $x_1 = s$, стоком -- вершина $x_2 = t$. Поток $phi = 0$.

= Получение полного потока

Определим, итерационно применяя теорему 1, полный поток $phi_n$.

== Путь $(x_1, x_2, x_7, x_8, x_10, x_11, x_12)$

Рассмотрим путь  $(x_1, x_2, x_7, x_8, x_10, x_11, x_12)$.

#img(image("2.png", width:90%), [Путь $(x_1, x_2, x_7, x_8, x_10, x_11, x_12)$, отмеченный на графе])

Рассчитаем остаточную пропускную способность пути:

#let fd(x1,x2) = {$space c(x_#x1, x_#x2) - phi(x_#x1, x_#x2)$}

$ delta^* = min{fd(1,2),fd(2,7),\ fd(7,8), fd(8,10),\ fd(10,11), fd(11,12)} = \ 
= min{13 - 0, 20 - 0, 8 - 0, 22 - 0, 17 - 0, 7 - 0}=\ = min{13, 20, 8, 22, 17, 7} = 7\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $


#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.
#pagebreak()
#img(image("3.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_11, x_12)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 0 + delta^* = 7$.

В результате, после выполнения всех действий получаем граф:

#img(image("4.png", width:80%), [Граф с текущими потоками])

== Путь $(x_1, x_2, x_7, x_10, x_11, x_9, x_12)$

Рассмотрим путь  $(x_1, x_2, x_7, x_10, x_11, x_9, x_12)$.

#img(image("5.png", width:90%), [Путь $(x_1, x_2, x_7, x_10, x_11, x_9, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1,2),fd(2,7),\ fd(7,10), fd(10,11),\ fd(11, 9), fd(9,12)} = \
= min{13 - 7, 20 - 7, 13 - 0, 17 - 7, 22 - 0, 18 - 0}=\ = min{6,13,13,10,22,18} = 6\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("6.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_1, x_2)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 7 + delta^* = 13$.

В результате, после выполнения всех действий получаем граф:

#img(image("7.png", width:80%), [Граф с текущими потоками])

== Путь $(x_1, x_5, x_7, x_12)$

Рассмотрим путь  $(x_1, x_5, x_7, x_12)$.

#img(image("8.png", width:90%), [Путь $(x_1, x_5, x_7, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1,5),fd(5,7),\ fd(7,12)} = min{26 - 0, 15 - 0, 31 - 0}=\ = min{26, 15, 31} 
= 15\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("9.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_5, x_7)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 13 + delta^* = 28$.

В результате, после выполнения всех действий получаем граф:

#img(image("10.png", width:80%), [Граф с текущими потоками])

== Путь $(x_1, x_5, x_8, x_10, x_11, x_9, x_12)$

Рассмотрим путь  $(x_1, x_5, x_8, x_10, x_11, x_9, x_12)$.

#img(image("11.png", width:90%), [Путь $(x_1, x_5, x_8, x_10, x_11, x_9, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 5), fd(5, 8),\ fd(8, 10), fd(10, 11),\ fd(11,9), fd(9,12)}\ = min{26 - 15, 14 - 0, 22 - 7, 17 - 13, 22 - 6, 18 - 6}\ = min{11, 14, 15, 4, 16, 12} = 4\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("12.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_10, x_11)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 28 + delta^* = 32$.

В результате, после выполнения всех действий получаем граф:

#img(image("13.png", width:80%), [Граф с текущими потоками])

#pagebreak()
== Путь $(x_1, x_5, x_8, x_10, x_12)$

Рассмотрим путь  $(x_1, x_5, x_8, x_10, x_12)$.

#img(image("14.png", width:90%), [Путь $(x_1, x_5, x_8, x_10, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 5), fd(5, 8),\ fd(8, 10), fd(10,12)}\ = min{26 - 19, 14 - 4, 22 - 11, 50 - 0}\ = min{7, 10, 11, 50} = 7\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("15.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_1, x_5)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 32 + delta^* = 39$.

В результате, после выполнения всех действий получаем граф:

#img(image("16.png", width:80%), [Граф с текущими потоками])

== Путь $(x_1, x_4, x_6, x_9, x_8, x_10, x_12)$

Рассмотрим путь  $(x_1, x_4, x_6, x_9, x_8, x_10, x_12)$.

#img(image("17.png", width:90%), [Путь $(x_1, x_4, x_6, x_9, x_8, x_10, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 4), fd(4, 6),\ fd(6, 9), fd(9, 8),\ fd(8, 10), fd(10,12)}\ = min{46 - 0, 21 - 0, 16 - 0, 4 - 0, 22 - 18, 50 - 7} = \ = min{46, 21, 16, 4, 4, 43} = 4\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("18.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребра $(x_9, x_8)$ и $(x_8, x_10)$ стали насыщенными. 

Таким образом общий поток $phi_n = phi_n + delta^* = 39 + delta^* = 43$.

В результате, после выполнения всех действий получаем граф:

#img(image("19.png", width:80%), [Граф с текущими потоками])

#pagebreak()
== Путь $(x_1, x_4, x_6, x_9, x_10, x_12)$

Рассмотрим путь  $(x_1, x_4, x_6, x_9, x_10, x_12)$.

#img(image("20.png", width:90%), [Путь $(x_1, x_4, x_6, x_9, x_10, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 4), fd(4, 6),\ fd(6, 9), fd(9, 10)\ fd(10,12)}\ = min{46 - 4, 21 - 4, 16 - 4, 10 - 0, 50 - 11} = \ = min{42, 17, 12, 10, 39} = 10\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("21.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_9, x_10)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 43 + delta^* = 53$.

В результате, после выполнения всех действий получаем граф:

#img(image("22.png", width:80%), [Граф с текущими потоками])

== Путь $(x_1, x_4, x_6, x_9, x_12)$

Рассмотрим путь  $(x_1, x_4, x_6, x_9, x_12)$.

#img(image("23.png", width:90%), [Путь $(x_1, x_4, x_6, x_9, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 4), fd(4, 6),\ fd(6, 9), fd(9,12)}\ = min{46 - 14, 21 - 14, 16 - 14, 18 - 10} = \ = min{32, 7, 2, 8} = 2\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("24.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_6, x_9)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 53 + delta^* = 55$.

В результате, после выполнения всех действий получаем граф:

#img(image("25.png", width:80%), [Граф с текущими потоками])

#pagebreak()
== Путь $(x_1, x_4, x_11, x_9, x_12)$

Рассмотрим путь  $(x_1, x_4, x_11, x_9, x_12)$.

#img(image("26.png", width:90%), [Путь $(x_1, x_4, x_11, x_9, x_12)$])

Рассчитаем остаточную пропускную способность пути:

$ delta^* = min{fd(1, 4), fd(4, 11),\ fd(11, 9), fd(9,12)}\ = min{46 - 16, 24 - 0, 22 - 10, 18 - 12} = \ = min{30, 24, 12, 6} = 6\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt) Добавим к потоку всех ребер, входящих в путь, остаточную пропускную способность пути. Ребра, пропускная способность которых будет равна потоку через ниx, станут насыщенными.

#img(image("27.png", width:80%), [Граф с добавленными потоками через ребра пути])

В данном случае ребро $(x_9, x_12)$ стало насыщенным. 

Таким образом общий поток $phi_n = phi_n + delta^* = 55 + delta^* = 61$.

В результате, после выполнения всех действий получаем граф:

#img(image("28.png", width:80%), [Граф с текущими потоками])

== Почему больше нет путей от источника к стоку?

В процессе выполнения данного пункта мы строим пути, проходящие только через ненасыщенные ребра, таким образом из источника можно начать строить путь только через ребро $(x_1, x_4)$. Из вершины $x_4$ ведут 2 ребра. Данные ребра ненасыщенны, поэтому можно продолжить построение пути по ним. Одно из ребер ведет в вершину $x_6$, из которой исходит только одно ребро, но оно насыщенно, поэтому по данному ребру из $x_4$ построить путь невозможно. Второе ребро ведет в вершину $x_11$, оно ненасыщенно. Из $x_11$ исходят 2 ребра, но одно из них насыщенно, поэтому из вершины $x_11$ путь может проходить только в вершину $x_9$. Из данной вершины исходят только насыщенные ребра, поэтому дальнейшее построение пути до стока невозможно.

== Полученный граф и полный поток

После применения теоремы 1 получили граф с насыщенными ребрами (выделены цветом на рис. 29).

#img(image("29.png", width:80%), [Граф с текущими потоками])

Полный поток получился равным $phi_n = 61$. 

== Проверки

Посчитаем сумму потоков ребер, исходящих из вершины $x_1$.

$ phi_x_1 = phi(x_1, x_2) + phi(x_1, x_4) + phi(x_1, x_5) = 13 + 26 + 22 = 61 = phi_n $

#h(35pt)Посчитаем сумму потоков ребер, приходящих в вершину $x_12$.

$ phi_x_12 = phi(x_7, x_12) + phi(x_9, x_12) + phi(x_10, x_12) + phi(x_11, x_12) =\ = 15 + 21 + 18 + 7 = 61 = phi_x_1 = phi_n $

#h(35pt)Значения исходящего из истока, входящего в сток и общего потока совпали.

Построим матрицу потоков ребер.

#align(center)[
  #tablex(
    columns: 13,
    inset: 10pt,
    align: center + horizon,
    [],[$x_1$],[$x_2$],[$x_3$],[$x_4$],[$x_5$],[$x_6$],[$x_7$],[$x_8$],[$x_9$],[$x_10$],[$x_11$],[$x_12$],
    [$x_1$], [  ],[13],[  ],[22],[26],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_2$], [  ],[  ],[  ],[  ],[  ],[  ],[13],[  ],[  ],[  ],[  ],[  ],
    [$x_3$], [  ],[  ],[  ],[  ],[  ],[0 ],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_4$], [  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[  ],[  ],[ 6],[  ],
    [$x_5$], [  ],[  ],[ 0],[  ],[  ],[  ],[15],[11],[  ],[  ],[  ],[  ],
    [$x_6$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[  ],
    [$x_7$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[7 ],[  ],[ 6],[  ],[15],
    [$x_8$], [  ],[  ],[ 0],[  ],[  ],[  ],[  ],[  ],[  ],[22],[  ],[  ],
    [$x_9$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[4 ],[  ],[10],[  ],[18],
    [$x_10$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[17],[21],
    [$x_11$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[7],
    [$x_12$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
)]


#h(35pt)По данной таблице можно посчитать сумму входящего потока и исходящего для любой вершины. Эти потоки будут равны (за исключением вершин источника и стока). Для подсчета входящего потока вершины $x_n$ суммируем все значения столбца $x_n$ таблицы, для подсчета исходящего потока суммируем все значения строки.

#align(center)[
  #tablex(
    columns: 3,
    inset: 10pt,
    align: center + horizon,
    [Вершина],[Входящий\ поток],[Исходящий\ поток],
    [$x_1$], [  ],[61],
    [$x_2$], [13],[13],
    [$x_3$], [0],[0],
    [$x_4$], [22],[22],
    [$x_5$], [26],[26],
    [$x_6$], [16],[16],
    [$x_7$], [28],[28],
    [$x_8$], [22],[22],
    [$x_9$], [32],[32],
    [$x_10$],[38],[38],
    [$x_11$],[23],[23],
    [$x_12$],[61],[  ],
)]

= Оптимизация

Итерационно используя теорему 2, увеличиваем полный поток.

== Увеличивающий маршрут $(x_1, x_4, x_11, x_10, x_12)$

Выполним разметку вершин, необходимо пометить вершину стока.
Для начала пометим знаком + источник $x_1$.
Каждую следующую вершину помечаем номером предыдущей со знаком + или -:

- Со знаком +, если ребро направлено из предыдущей вершины (последней помеченной) в помечаемую и оно строго ненасыщенно (в данном случае ребро называется прямым),
- Со знаком -, если ребро противоположно направлено и его поток не равен 0 (само ребро называется обратным).

Таким образом получилось отметить 5 вершин

#align(center)[
  #tablex(
    columns: 2,
    inset: 10pt,
    align: center + horizon,
    [Вершина],[Пометка],
    [$x_1$], [+],
    [$x_4$], [+1],
    [$x_11$], [+4],
    [$x_10$], [-11],
    [$x_12$], [+10],
 )]

#img(image("30.png", width:80%), [Граф с метками])

Ребра, которые направлены на вершины с метками + (прямые ребра) обозначим синим, а те, которые противоположно направлены на вершины с метками - (обратные ребра) обозначим оранжевым.

Рассчитаем остаточную пропускную способность синих (прямых) ребер.

$ delta^* = min{fd(1, 4), fd(4, 11),  fd(10,12)}=\ = min{46 - 22, 24 - 6, 50 - 21} = min{24, 18, 29} = 18\ c(x_i, x_j) "- пропускная способность ребра с вершинами" x_i space и space x_j \ phi(x_i, x_j) "- поток ребра с вершинами" x_i space и space x_j $

#h(35pt)Найдем минимальный поток оранжевых (обратных) ребер.

$ phi^* = min{phi(10,11)} = min{17} = 17 $

$ epsilon^* = min{delta^*, phi^*} = min{18, 17} = 17 $

#h(35pt)Поток в сети можно увеличить на 17 единиц ($phi_max = phi_n +17 = 78$) за счет данного увеличивающего маршрута. Увеличим поток на синих (прямых) ребрах на $epsilon^*$ и уменьшим на оранжевых (обратных) на то же значение.

#img(image("31.png", width:80%), [Граф с оптимизированным распределением потоков])

Так как на оранжевом (обратном) ребре поток уменьшился можно сделать вывод, что ребро $(x_10, x_11)$ перестало быть насыщенным.

В результате, после выполнения всех действий получаем граф:

#img(image("32.png", width:80%), [Граф с текущими потоками])

== Почему больше нет увеличивающих маршрутов?

Попробуем пометить еще один увеличивающий маршрут. 
Пометим $x_1$ знаком +. Из $x_1$ можно попасть только в вершину $x_4$, так как $x_1$ не является концом ребра, ни одну вершину мы не можем пометить знаком -, а знаком + можем пометить, только ту, ребро которой не является насыщенным.

Таким образом помечаем $x_4$ как +1. Вершина $x_4$ является концом ребра, начало которого в $x_1$, таким образом вершина $x_1$ может быть помечена как -4, но так как из $x_1$ можно пометить только $x_4$ помечать $x_1$ второй раз не целесообразно.

Вершина $x_4$ является началом 2 ненасыщенных ребер, это означает, что мы можем пометить одну из двух вершин меткой +4. Если мы пометим вершину $x_6$, то будет невозможно пометить $x_9$, так как ребро насыщенно, и $x_3$, так как поток, проходящий через ребро равен 0. Таким образом из вершины $x_6$ можно пометить только вершину -- $x_4$.

Попробуем вернуться на пару шагов назад и пометить $x_11$ вместо $x_6$. Так как больше ничего пометить мы не можем (остальные маршруты не могут привести к стоку) далее будем рассматривать все относительно вершины $x_11$. Помечать $x_4$ нет смысла. Поэтому дальше пометить мы можем только $x_9$.

Меткой -9 можно пометить $x_11$, но помечать данную вершину нет смысла. Меткой +9 мы не можем пометить ни одну из вершин, так как все ребра, началом которых является $x_9$, насыщены. Остается рассмотреть только возможность пометки вершины $x_6$ меткой -9: из нее мы можем попасть только в вершину $x_4$ и далее вести рассуждения так же, как и во втором абзаце.

Таким образом любые попытки пометить сток приводят нас к циклу, в котором мы помечаем одни и те же вершины разными метками, но при этом сток пометить не удается, поэтому можно утверждать, что больше нет увеличивающих маршрутов.

Поэтому по теореме 3 можно утверждать, что полный поток равен максимальному.

#pagebreak()
== Полученный граф и общий поток

Получили граф с максимальным общим потоком.

#img(image("32.png", width:80%), [Граф с максимальным общим потоком])

Максимальный общий поток получился равным $phi_max = 78$. 
#pagebreak()
== Проверки

Посчитаем сумму потоков ребер, исходящих из вершины $x_1$.

$ phi_x_1 = phi(x_1, x_2) + phi(x_1, x_4) + phi(x_1, x_5) = 13 + 26 + 38 = 78 = phi_max $

#h(35pt)Посчитаем сумму потоков ребер, приходящих в вершину $x_12$.

$ phi_x_12 = phi(x_7, x_12) + phi(x_9, x_12) + phi(x_10, x_12) + phi(x_11, x_12) =\ = 15 + 38 + 18 + 7 = 78 = phi_x_1 = phi_max $

#h(35pt)Значения исходящего из истока, входящего в сток и общего потока совпали.

Построим матрицу потоков ребер.

#align(center)[
  #tablex(
    columns: 13,
    inset: 10pt,
    align: center + horizon,
    [],[$x_1$],[$x_2$],[$x_3$],[$x_4$],[$x_5$],[$x_6$],[$x_7$],[$x_8$],[$x_9$],[$x_10$],[$x_11$],[$x_12$],
    [$x_1$], [  ],[13],[  ],[39],[26],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_2$], [  ],[  ],[  ],[  ],[  ],[  ],[13],[  ],[  ],[  ],[  ],[  ],
    [$x_3$], [  ],[  ],[  ],[  ],[  ],[0 ],[  ],[  ],[  ],[  ],[  ],[  ],
    [$x_4$], [  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[  ],[  ],[23],[  ],
    [$x_5$], [  ],[  ],[ 0],[  ],[  ],[  ],[15],[11],[  ],[  ],[  ],[  ],
    [$x_6$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[  ],
    [$x_7$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[7 ],[  ],[ 6],[  ],[15],
    [$x_8$], [  ],[  ],[ 0],[  ],[  ],[  ],[  ],[  ],[  ],[22],[  ],[  ],
    [$x_9$], [  ],[  ],[  ],[  ],[  ],[  ],[  ],[4 ],[  ],[10],[  ],[18],
    [$x_10$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[ 0],[38],
    [$x_11$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[16],[  ],[  ],[7],
    [$x_12$],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],[  ],
)]


#h(35pt)По данной таблице можно посчитать сумму входящего потока и исходящего для любой вершины. Эти потоки будут равны (за исключением вершин источника и стока). Для подсчета входящего потока вершины $x_n$ суммируем все значения столбца $x_n$ таблицы, для подсчета исходящего потока суммируем все значения строки.

#align(center)[
  #tablex(
    columns: 3,
    inset: 10pt,
    align: center + horizon,
    [Вершина],[Входящий\ поток],[Исходящий\ поток],
    [$x_1$], [  ],[78],
    [$x_2$], [13],[13],
    [$x_3$], [0],[0],
    [$x_4$], [39],[39],
    [$x_5$], [26],[26],
    [$x_6$], [16],[16],
    [$x_7$], [28],[28],
    [$x_8$], [22],[22],
    [$x_9$], [32],[32],
    [$x_10$],[38],[38],
    [$x_11$],[23],[23],
    [$x_12$],[78],[  ],
)]

#h(35pt)Напишем код, который считает максимальный поток по входной матрице пропускных способностей. Результатом работы кода тоже является число 78.

#img(image("34.png", width:40%), [Вывод кода])

#let code = (read("code.cpp"))
#set text(10.5pt)
#raw(code, lang:"cpp")
#set text(14pt)

= Построение минимального разреза

Для любой сети с одним источником и одним стоком величина максимального потока, доставляемая от источника к стоку равна пропускной способности минимального разреза.

// Если из сети исключить прямые и насыщенные ребра, а так же обратные, поток которых равен 0, то сеть разбивается на 2 компонента связности, причем источник и сток оказываются в разных компонентах.

Пусть подмножество вершин, оставшихся непомеченными при попытке построить увеличивающий маршрут будет $A = {x_2, x_3, x_5, x_7, x_8, x_10, x_12}$, тогда 

$ phi_t = sum phi(U_i) - sum phi(U_j) $

$ U_i in U_A^+ - "подмножество ребер, заходящих в вершины подмножества A" $
$ U_j in U_A^- - "подмножество ребер, исходящих из вершин подмножества A" $

#h(35pt) В случае максимального потока $sum phi(U_j) = 0$, тогда:
$ phi_t = sum phi(U_i) $

#h(35pt)Все ребра из $U_A^+$ являются насыщенными и $sum phi(U_i) = phi_max$ сумма пропускных способностей дает максимальный поток. Именно эти ребра образуют минимальный разрез.

Насыщенные ребра имеют свойства: начальная вершина $in X$ ($X = {x_1, x_4, x_6, x_9, x_11}$ - вершины, которые удалось пометить), конечная в подмножестве A. Таким образом получаем, что разрез будет проходить между теми вершинами, которые удалось пометить и теми, которые пометить не удалось. Получаем разрез $(X arrow A)$:


#img(image("33.png", width:80%), [Разрез $(X arrow A)$])

Минимальный разрез в данной сети составляют ребра
$ (X arrow A) = {(x_1, x_2), (x_1, x_5), (x_9, x_8), (x_9, x_10), (x_9, x_12), (x_11, x_12)} $

#h(35pt)Рассчитаем пропускную способность минимального разреза
$ C(X arrow A) = C(x_1, x_2) + C(x_1, x_5) + C(x_9, x_8) + C(x_9, x_10) +\ + C(x_9, x_12) + C(x_11, x_12) = 13 + 26 + 4 + 10 + 18 + 7 = 78 $

#h(35pt)Пропускная способность минимального разреза совпала с максимальным потоком сети.

= Вывод

- Для определения полного потока было исследовано 9 путей, был достигнут полный поток $phi_n = 61$. Был проверен баланс.
- В оптимизационной части алгоритма был построен 1 увеличивающий маршрут, который увеличил полный поток, полученный в предыдущем пункте на 17 единиц, полный поток стал равен максимальному. Был проверен баланс и написан код по поиску максимального потока в сети, вывод программы совпал с максимальным потоком $phi_max = 78$.
- В минимальном разрезе 6 ребер оказались насыщенными, пропускная способность минимального разреза совпала с максимальным потоком. Условие теоремы Форда-Фалкерсона не нарушено, максимальный поток найден верно.

#img(image("32.png", width:80%), [Получившийся граф])
