Дан ориентированный граф с множеством вершин V=s. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Дан ориентированный граф с множеством вершин V=s

Дан ориентированный граф с множеством вершин V=s .pdf

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

Условие

Дан ориентированный граф с множеством вершин V=s,1,2,3,4,5,t и множеством ребер – ориентированных дуг R=s,1,s,2,s,3,1,4,1,2,2,4,2,5,3,2,3,5,5,4,5,t,(4,t) Орграф задает сеть по передаче нефти. Необходимо найти максимальный поток в сети, если пропускная способность участков сети следующая: cs1=26, cs2=55,cs3=29, c14=23, c12=70, c24=20, c25=18, c32=20, c35=16, c54=5, c5t=64, c4t=96. Указать метод решения задачи оптимизации.

Нужно полное решение этой работы?

Решение

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

Алгоритм отыскания максимального потока в сети называется алгоритмом Форда – Фалкерсона (алгоритм расстановки пометок).
Источник – вершина s, сток – вершина t.
С помощью алгоритма Форда-Фалкерсона найдем наибольший поток из s в t.
Шаг 1. Выбираем произвольный поток, например, s-3-5-t. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 109. Уменьшаем пропускные способности дуг этого потока на 16, насыщенную дугу 3-5 вычеркиваем.
Шаг 2 . Выбираем произвольный поток, например, s-3-2-5-t. Его пропускная способность равна минимальной и равна 99. Уменьшаем пропускные способности дуг этого потока на 13, насыщенную дугу s-3 вычеркиваем.
Шаг 3. Выбираем произвольный поток, например, s-2-5-t. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг и равна 95. Уменьшаем пропускные способности дуг этого потока на 5, насыщенную дугу 2-5 вычеркиваем.
Шаг 4

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

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

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