Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм построения максимального потока в транспортной сетиСодержание книги
Поиск на нашем сайте Алгоритм построения максимального потока в транспортной сети D: Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x Î X). Шаг 2. По сети D и потоку ji строим орграф приращений I(D, ji). Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в vn в нагруженном орграфе I(D, ji) (например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна ¥, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai Î Z (прибавляя ее для каждой дуги x Î X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны). Пример 92.
Решение. Для решения используем алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе. Построим матрицу длин дуг C(D) и l -матрицу (табл. 69). Таблица 69
Поскольку Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v1 в v6 в орграфе приращений равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5, где i1 = 6. Получаем, что в качестве такой последовательности надо взять номера 1, 3, 2, 5, 6, так как
Тогда v1v3v2v5v6 – искомый нулевой путь из v1 в v6. Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-». Получаем, min{8-2=6, 2, 6-2=4, 9-4=5}=2. Перемещаем по контуру 2.
Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 11. Проверим, является ли он максимальным. Построим матрицу длин дуг C(D) и l -матрицу (табл. 70). Таблица 70
Так как
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2017-02-07; просмотров: 247; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.217.21 (0.006 с.) |
Выяснить является ли полный поток максимальным (рис. 51), если нет, то дополнить его до максимального.
, то существует нулевой путь из источника v1 в сток v6. Значит, полный поток не является максимальным. Дополним его до максимального. Для этого найдем путь нулевой длины: 
Теперь необходимо найти величину, которую будем перемещать по полученному контуру. Для этого, каждому ребру в контуре поставим в соответствие число a(i, j), которое находим по следующему правилу: если направление ребра (i, j) в контуре совпадает с направлением ребра x в транспортной сети, то a(i, j)=с(х)-j(х); если направление ребра в контуре не совпадает с направлением ребра в транспортной сети, то a(i, j)=j(х). Итак, из чисел a(i, j) найдем минимальное:
В результате получаем поток, изображенный на рисунке 52.
, то нулевого пути из v1 в v6 не существует. Значит, поток 
является максимальным.
