Максимальный поток в сети

1.

1
Тема 3.5
Максимальный поток в
сети

2.

Содержание
1. Постановка задачи о максимальном потоке
2. Алгоритм Форда-Фалкерсона нахождения
максимального потока
2

3.

Постановка задачи о максимальном потоке
3
Транспортной сетью называют связный граф без циклов,
в котором:
существует единственная вершина s, из которой дуги
только выходят, называемая источником (входом)
сети;
существует единственная вершина t, в которую дуги
только заходят, называемая стоком (выходом) сети;
для каждой дуги (i, j) задан вес неотрицательным
целым числом сij, называемым пропускной
способностью дуги.

4.

Постановка задачи о максимальном потоке
Потоком в сети называется целочисленная функция,
заданная на дугах графа, такая, что:
1) для любой дуги 0 ij сij;
2) для любой вершины i, кроме источника и стока сети,
имеет место равенство
෍