По матрице пропускных способностей дуг графа G найти максимальный поток от вершины s = x1 до вершины t = x7 и указать минимальный разрез. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
По матрице пропускных способностей дуг графа G найти максимальный поток от вершины s = x1 до вершины t = x7 и указать минимальный разрез

По матрице пропускных способностей дуг графа G найти максимальный поток от вершины s = x1 до вершины t = x7 и указать минимальный разрез .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

По матрице пропускных способностей дуг графа G найти максимальный поток от вершины s = x1 до вершины t = x7 и указать минимальный разрез, отделяющий s от t. =--5-159-----6-7-3-4-7------83-----918------5-------

Решение

Потяни, чтобы посмотреть

С помощью алгоритма Форда-Фалкерсона найдем наибольший поток из x1 в x7.
Шаг 1. Выбираем произвольный поток, например, x1 – x3 – x2 – x7. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 3. Уменьшаем пропускные способности дуг этого потока на 3, насыщенную дугу x3 – x2 вычеркиваем.
Шаг 2. Выбираем произвольный поток, например, x1 – x3 – x4 – x7 . Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 2. Уменьшаем пропускные способности дуг этого потока на 2, насыщенную дугу x1 – x3 вычеркиваем.
Шаг 3. Выбираем произвольный поток, например, x1 – x6 – x7. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 5

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу