Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда—Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
— исток сети; — сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r[0,1] = 39; r[4,7] = 44; r[6,3] = 33; r[5,7] = 53; r[0,2] = 10;
r[4,2] = 18; r[6,7] = 95; r[5,4] = 16; r[0,3] = 23; r[2,5] = 61;
r[2,1] = 81; r[6,5] = 71; r[1,4] = 25; r[2,6] = 15; r[3,2] = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток — это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.

4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.

5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.

6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки ( красные круги)

Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы — в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети
Вычисление величины максимального потока