Построй граф маршрутов и подпиши на каждой дуге остаточную пропускную способность после работы алгоритма. Выдели дуги, составляющие минимальный разрез. Транспортная сеть между терминалами A и Z: Узлы: A (источник), B, C, D, E, Z (сток) Дуги (и пропускные

Построй граф маршрутов и подпишите на каждой дуге остаточную пропускную способность после работы алгоритма. Выделите дуги, составляющие минимальный разрез. на основании следующей информации: "
1. Анализ Исходных Данных, у нас есть следующая транспортная сеть между терминалами A и Z:
Узлы: A (источник),B,C,D,E,Z (сток)
Дуги (и пропускные способности):
A-B:10 тонн/час
A-C:15 тонн/час
B-D:8 тонн/час
B-E:5 тонн/час
C-D:10 тонн/час
C-E:12 тонн/час
D-Z:18 тонн/час
E-Z:20 тонн/час
2. Определение Максимального Потока (Алгоритм Форда-Фалкерсона)
Применим алгоритм Форда-Фалкерсона. Для упрощения представим несколько итераций:
Итерация 1: Путь A-B-D-Z. Минимальная пропускная способность на этом пути: min(10, 8, 18) = 8. Пропускаем 8 тонн/час.
Обновляем пропускные способности:
A-B:2
B-D:0
D-Z:10
Добавляем обратные дуги (для алгоритма):
B-A:8
D-B:8
Z-D:8
Итерация 2: Путь A-C-E-Z. Минимальная пропускная способность: min(15, 12, 20) = 12. Пропускаем 12 тонн/час.
Обновляем пропускные способности:
A-C:3
C-E:0
E-Z:8
Добавляем обратные дуги:
C-A:12
E-C:12
Z-E:12
Итерация 3: Путь A-C-D-Z. Минимальная пропускная способность: min(3, 10, 10) = 3. Пропускаем 3 тонны/час.
Обновляем пропускные способности:
A-C:0
C-D:7
D-Z:7
Добавляем обратные дуги:
C-A:15
D-C:3
Z-D:3
Итерация 4: Путь A-B-E-Z. Минимальная пропускная способность: min(2, 5, 8) = 2. Пропускаем 2 тонны/час.
Обновляем пропускные способности:
A-B:0
B-E:3
E-Z:6
Добавляем обратные дуги:
B-A:10
E-B:2
Z-E:2
Итерация 5: Путь A-B-D-C-E-Z. (Более сложный путь). Минимальная пропускная способность: min(0, 0, 3, 7, 12, 6)=0. Этот путь не увеличивает поток.
Алгоритм завершается, когда больше нет путей из A в Z с положительной пропускной способностью.
Максимальный поток=8+12+3+2=25 тонн/час.
Поиск минимального разреза
В нашем случае, если после завершения алгоритма мы не можем достичь Z из A, то разрезающие дуги-это те, которые ведут из достижимого множества узлов в недостижимое.
В нашем случае, минимальный разрез состоит из дуг:
D-Z:18
E-Z:7