Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.
На каждом из ребер проставлены значения пропускной способности С (n) ребра n.
Для заданной сети определить максимальный поток jmax транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.
Решение:
Максимальный поток jmax транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:
Первый шаг.1. Находим какой-либо путь из х 1 в х 9 с положительной пропускной способностью.
Tаблица 1.
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (3) | x8 (2) | x9 (6) | |
| x1 | 9- | ||||||||
| x2 | |||||||||
| x3 | 0+ | 8- | |||||||
| x4 | |||||||||
| x5 | |||||||||
| x6 | 0+ | 3- | |||||||
| x7 | |||||||||
| x8 | |||||||||
| x9 | 0+ |
В результате получен путь l1 = (x1, х3, х6, х9). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов 
табл.1 вычитаем C1, а к элементам 
прибавляем C1. В результате получим новую табл.2 с измененными пропускными способностями.
Tаблица 2
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (3) | x8 (2) | x9 (7) | |
| x1 | 6- | ||||||||
| x2 | |||||||||
| x3 | 3+ | 4- | |||||||
| x4 | |||||||||
| x5 | |||||||||
| x6 | |||||||||
| x7 | 0+ | 6- | |||||||
| x8 | |||||||||
| x9 | 0+ |
Второй шаг .1. Помечаем столбцы табл.2, находим второй путь l2 = (x1,x3, х7, х9) и расставляем знаки.
2. Пропускная способность пути l2
Изменим пропускные способности помеченных дуг на С2 в табл.3.
Tаблица 3
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (4) | x8 (2) | x9 (7) | |
| x1 | 4- | ||||||||
| x2 | |||||||||
| x3 | |||||||||
| x4 | 0+ | 9- | |||||||
| x5 | |||||||||
| x6 | |||||||||
| x7 | 0+ | 2- | |||||||
| x8 | |||||||||
| x9 | 4+ |
Третий шаг.1. Пометив столбцы, находим l3 = (x1, х4, х7,x9).
Величина потока по пути l3
Вычислив новые пропускные способности дуг, приходим к табл.4.
Таблица 4
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (4) | x8 (2) | x9 (8) | |
| x1 | 7- | ||||||||
| x2 | 0+ | 6- | |||||||
| x3 | |||||||||
| x4 | |||||||||
| x5 | |||||||||
| x6 | |||||||||
| x7 | |||||||||
| x8 | 0+ | 8- | |||||||
| x9 | 0+ |
Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l4 = (x1, х2, х8, х9) и расставляем знаки.
2. Пропускная способность пути l4
Изменим пропускные способности помеченных дуг на С4 в табл.5.
Таблица 5
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (4) | x8 (4) | x9 (8) | |
| x1 | 2- | ||||||||
| x2 | |||||||||
| x3 | |||||||||
| x4 | 2+ | 2- | |||||||
| x5 | |||||||||
| x6 | |||||||||
| x7 | |||||||||
| x8 | 0+ | 2- | |||||||
| x9 | 6+ |
Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l5 = (x1, х4, х8, х9) и расставляем знаки.
2. Пропускная способность пути l5
Изменим пропускные способности помеченных дуг на С5 в табл.6.
Таблица 6
| x1 | x2 (1) | x3 (1) | x4 (1) | x5 (2) | x6 (3) | x7 (4) | x8 (5) | x9 | |
| x1 | |||||||||
| x2 | |||||||||
| x3 | |||||||||
| x4 | |||||||||
| x5 | |||||||||
| x6 | |||||||||
| x7 | |||||||||
| x8 | |||||||||
| x9 |
Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x1 в вершину x9. Подмножество R образуют помеченные вершины х1, х2, х3, х4, х5, х6, х7, х8, а подмножество 
- одна непомеченная вершины х9. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные - . Таким образом, разрез с минимальной пропускной способностью 
. Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза
Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7
Таблица 7.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | |
| x1 | |||||||||
| x2 | -6 | ||||||||
| x3 | -7 | ||||||||
| x4 | -4 | ||||||||
| x5 | |||||||||
| x6 | -3 | ||||||||
| x7 | |||||||||
| x8 | -6 | -2 | |||||||
| x9 | -3 | -6 | -8 |
Величина максимального потока равна сумме элементов x1 -й строки табл.7 или сумме элементов x9 -го столбца.
Максимальный поток равен 
.