Максимальный поток. Определить максимальный поток для сети заданной в табличном виде. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Максимальный поток. Определить максимальный поток для сети заданной в табличном виде

Максимальный поток. Определить максимальный поток для сети заданной в табличном виде .pdf

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

Условие

Максимальный поток Определить максимальный поток для сети заданной в табличном виде Начало дуги (i) 0 0 1 1 2 2 3 3 4 4 5 Конец дуги(j) 1 4 2 5 5 3 6 5 5 6 6 Пропускная способность t(i,j) 5 7 3 7 4 1 2 4 9 5 3

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

Решение

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

Построим сетевую модель
Итерация_1.
Шаг_1. Назначаем a0=∞ и помечаем узел 0 меткой [беск.; -]. Полагаем i=0.
Шаг_2. S1=0,4 (множество не пустое).
Шаг_3. k=7, поскольку maxc01;c04=max5;7=7. Назначаем a4=c04=7 и помечаем узел 4 меткой 7;0. Полагаем i=4 и возвращаемся к шагу 2.
Шаг_2*. S4=5,6
Шаг_3*. k=5 и a5=c45=maxc45;c46=max9;5=9. Помечаем узел 5 меткой 9;4. Полагаем i=5 и возвращаемся к шагу 2.
Шаг_2*. S5=6
Шаг_3*. k=6 и a6=c56=3. Помечаем узел 6 меткой 3;5. Получен сквозной путь. Перейдем к шагу 5.
Шаг_5. Сквозной путь определяется по меткам, начиная с узла 6 и заканчивая узлом 1:
6→3;5→5→9;4→4→7;0→0
Таким образом, N1=0,4,5,6 и f1=mina0,a4,a5,a6=min∞,7,9,3=3. Вычисляем остаточные пропускные способности вдоль пути N1:
c04;c40=7-3;0+3=4;3
c45;c54=9-3;0+3=6;3
c56;c65=3-3;0+3=0;3
Итерация_2 . Аналогично для пути 0-1-2-3-6.
Шаг_1. Назначаем a0=∞ и помечаем узел 0 меткой [беск.; -]. Полагаем i=0.
Шаг_2. S0=0,4 (множество не пустое).
Шаг_3. k=5, поскольку maxc01;c04=max5;4=5. Назначаем a1=c01=5 и помечаем узел 1 меткой 5;1. Полагаем i=1 и возвращаемся к шагу 2.
Шаг_2*. S1=2 (отметим, что c56=0, поэтому узел 5 не включается в S2)
Шаг_3*. k=2 и a2=c12=3. Помечаем узел 2 меткой 3;1. Полагаем i=2 и возвращаемся к шагу 2.
Шаг_2*. S2=3
Шаг_3*. k=3 и a3=c23=1. Помечаем узел 3 меткой 1;2. Полагаем i=3 и возвращаемся к шагу 2.
Шаг_2*. S3=6
Шаг_3*. k=6 и a6=c36=2. Помечаем узел 6 меткой 2;6. Получен сквозной путь. Перейдем к шагу 5.
Шаг_5. Сквозной путь определяется по меткам, начиная с узла 6 и заканчивая узлом 1:
6→2;3→3→1;2→2→3;1→1→5;0→0
Таким образом, N2=0,1,2,3,6 и f2=mina0,a1,a2,a3,a6=min∞,5,3,1,2=1.
Вычисляем остаточные пропускные способности вдоль пути N2:
c01;c10=5-1;0+1=4;1
c12;c21=3-1;0+1=2;1
c23;c32=1-1;0+1=0;1
c36;c63=2-1;0+1=1;1
Итерация_3

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

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

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