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

⇐ Предыдущая 10 11 12 13 141516 17 18 19 Следующая ⇒

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.

⇐ Предыдущая 10 11 12 13 141516 17 18 19 Следующая ⇒

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

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Оценка качества Анализ документации. Имеющийся рецепт, паспорт письменного контроля и номер лекарственной формы соответствуют друг другу. Ингредиенты совместимы, расчеты сделаны верно, паспорт письменного контроля выписан верно. Правильность упаковки и оформления....

БИОХИМИЯ ТКАНЕЙ ЗУБА В составе зуба выделяют минерализованные и неминерализованные ткани...

Типология суицида. Феномен суицида (самоубийство или попытка самоубийства) чаще всего связывается с представлением о психологическом кризисе личности...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Устройство рабочих органов мясорубки Независимо от марки мясорубки и её технических характеристик, все они имеют принципиально одинаковые устройства...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

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