.

По не насыщенным дугам найдем путь из источника к стоку:

. Вдоль этого пути пустим дополнительный поток , мощность которого будет равна: . Пересчитаем матрицу смежности:

и найдем новый путь от источника к стоку: . Вдоль этого пути пустим дополнительный поток , мощность которого будет равна: . Пересчитаем матрицу смежности:

7

. В полученной сети уже не существует пути ведущего от источника к стоку: из вершины 1 можно попасть только в вершины 3 и 2.

Следовательно, построен максимальный поток, мощность которого равна 12 + 3 + 5 = 20:



и найдено минимальное сечение , состоящее из всех дуг, соединяющих множество вершин с вершиной 4.

Проверим это, вычислив пропускную способность сечения :

---

Смотрите также файлы

• Управление качеством.docx

• Краткое содержание Продукт проекта. Детская деятельность в условиях обогащенной среды Месяц.docx

• Любовь спасет мир.docx

• Отчет по прохождению производственной практики (по профилю специальности) По профессиональному модулю.docx

• Курсовая работа 09. 02. 07 Информационные системы и программирование код и наименование специальности.docx