Студопедия — Алгоритм построения максимального потока в сети
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм построения максимального потока в сети


⇐ Предыдущая10111213141516171819Следующая ⇒




1. Если поток в сети не задан,

то считать поток нулевым.

2. Пока в сети есть увеличивающие цепи повторять:

· взять любую увеличивающую цепь,

· вычислить наименьшую разность d между пропускными способностями дуг этой цепи и потоками по этим дугам,

· потоки по дугам, направление которых совпадает с направлением потока, увеличить на d,

· потоки по дугам, направление которых противоположно направлению потока, уменьшить на d,

3. Если в сети нет увеличивающих цепей,

то максимальный поток построен,

Пример 1 (Поток в сети не задан). Построить максимальный поток для заданной транспортной цепи.

Данная сеть: Сеть с нулевым потоком:

Решение.

1. Поток в сети не задан, считаем его нулевым.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DF; направление дуг совпадает с направлением потока, d = min(9 – 0, 6 – 0, 10 – 0) = 6. Новые потоки по дугам цепи: AB: 0+6=6, BD: 0+6 = 6, DF: 0+6=6:

 

Увеличивающая цепь: AB, BE, EF; направление дуг совпадает с направлением потока, d = min(9 – 6, 3 – 0, 7 – 0) = 3. Новые потоки по дугам цепи: AB: 6 + 3 = 9, BE: 0 + 3 = 3, EF: 0 + 3 = 3:

 

Увеличивающая цепь: AC, CE, ED, DF; направление дуг совпадает с направлением потока, d = min(8 – 0, 4 – 0, 4 – 0, 10 – 6) = 4. Новые потоки по дугам цепи: AC: 0 + 4 = 4, CE: 0 + 4 = 4, ED: 0 + 4 = 4, DF: 6 +4 = 10:

Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Пример 2 (Поток в сети задан). Построить максимальный поток для заданной транспортной цепи.

Сеть с заданным потоком:

Решение.

1. Поток в сети задан.

2. Пока в сети есть увеличивающие цепи, повторяем:

Увеличивающая цепь: AB, BD, DE, EF; направление дуги DE противоположно потоку, направление остальных дуг совпадает с направлением потока, d = min(9 – 6, 6 – 3, 4 – 2, 7 – 4) = 2. Новые потоки по дугам цепи: AB: 6 + 2 = 8, BD: 3 + 2 = 5, DE: 2 – 2 = 0, EF: 4 + 2 = 6:

 

Увеличивающая цепь: AB, BD, DF; направление дуг совпадает с направлением потока, d = min(9 – 8, 6 – 5, 10 – 5) = 1. Новые потоки по дугам цепи: AB: 8 + 1 = 9, BD: 5 + 1 = 6, DF: 5 + 1 = 6:

 

Увеличивающая цепь: AC, CE, EF; направление дуг совпадает с направлением потока, d = min(8 – 3, 4 – 3, 7 – 6) = 1. Новые потоки по дугам цепи: AC: 3+ 1 = 4, CE 3+ 1 = 4, EF: 6 + 1 = 7:

Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.

Примечание. Обратите внимание на то, что сети в примерах 1 и 2 и максимальные потоки по ним совпадают, а потоки по некоторым дугам различаются, например, в примере 1 поток по дуге DF равен 10, а в примере 2 по этой же дуге равен 6.




⇐ Предыдущая10111213141516171819Следующая ⇒


Дата добавления: 2015-06-29; просмотров: 1371. Нарушение авторских прав; Мы поможем в написании вашей работы!

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Разновидности сальников для насосов и правильный уход за ними   Сальники, используемые в насосном оборудовании, служат для герметизации пространства образованного кожухом и рабочим валом, выходящим через корпус наружу...

Дренирование желчных протоков Показаниями к дренированию желчных протоков являются декомпрессия на фоне внутрипротоковой гипертензии, интраоперационная холангиография, контроль за динамикой восстановления пассажа желчи в 12-перстную кишку...

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Закон Гука при растяжении и сжатии   Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Характерные черты официально-делового стиля Наиболее характерными чертами официально-делового стиля являются: • лаконичность...

Этапы и алгоритм решения педагогической задачи Технология решения педагогической задачи, так же как и любая другая педагогическая технология должна соответствовать критериям концептуальности, системности, эффективности и воспроизводимости...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия