Найдите максимальный поток в заданной транспортной сети (s – начальная вершина. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Найдите максимальный поток в заданной транспортной сети (s – начальная вершина

Найдите максимальный поток в заданной транспортной сети (s – начальная вершина .pdf

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

Условие

Найдите максимальный поток в заданной транспортной сети (s – начальная вершина, t – конечная), используя алгоритм Форда-Фалкерсона. Проверьте ответ по теореме Форда-Фалкерсона (найдите минимальный разрез графа сети). s a b c t s 40 22 a 5 3 b 8 11 c 18 t

Решение

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

1. Начальный поток равен Valf=0
Путь из s в t, по которому поток может быть увеличен состоит из следующих дуг: s→a→t.
Расставляем пометки вершин: s=0;∞→+1;∆s=40-0=40→t=(+2;∆t=3-0=3). Добавка к потоку: min⁡(∆)=3
Строим новый поток f1,величины Valf1=Valf+3=3:
2. Путь из s в t, по которому поток может быть увеличен состоит из следующих дуг: s→b→t.
Расставляем пометки вершин: s=0;∞→+1;∆b=22-0=22→→t=(+2;∆t=11-0=11) . Добавка к потоку: min⁡(∆)=11
Строим новый поток f2,величины Valf2=Valf1+11=14:
3. Путь из s в t, по которому поток может быть увеличен состоит из следующих дуг: s→a→c→t.
Расставляем пометки вершин: s=0;∞→+1;∆a=40-3=39→+2;∆c=5-0=5→t=(+3;∆t=18-0=18). Добавка к потоку: min⁡(∆)=5
Строим новый поток f3,величины Valf3=Valf2+5=19:
4

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

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

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