Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 166

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 166)

Мы добавляем фикпиный исток з и ребра с бесконечной пропускной способностью от з до кюкдого ю исходных истоков. Кроме того, мы добавляем фиктивный сток г и ребра с бесконечной пропускной способностью иэ кандого иэ исходных истоков в г. Задача определения максимального потока в сети с несюлькнми истоками и несколькими спжами сводится к обычной задаче о максимальном потоке. На рис. 26.3,(б) показано, как сеть, представленную на рис. 26.3,(а), можно превратить в обычную транспортную сеть с одним истоюм и одним стоюэм. Для этого в сеть добавляются фиктивный исток (зпрегзопгсе) л и ориентированные реб- Часть Г7.

Алгоритмы длл работы с графами 752 ра (и, в,) с пропускной способностью с(в, вг) = оо для каждого г = 1, 2,..., т. Точно так же создается фнкнгнвный енгок (ааргеып1с) 1 и добавляются ориентированные ребра (г„г) с с(г„г) = оо для каждого 1 = 1, 2,..., п. Интуитивно понятно, что любой поток в сети на рис. 26.3, (а) соответствует потоку в сети на рис. 26.3, (б), и наоборот. Единственный исток в просто обеспечивает поток любой требуемой величины к истокам в;, а единственный сток г аналогичным образом потребляет поток любой желаемой величины от множественных стоков Ц. В упр. 26.1.2 предлагается формально доказать эквивалентность зтих двух задач.

Упражнения 26.1.1 Покажите, что разделение ребра в транспортной сети дает эквивалентную сеть. Говоря более формально, предположим, что транспортная сеть С содержит ребро (и, и), и мы создаем транспортную сеть С' путем добавления новой вершины х и замены (и,и) новыми ребрами (и,х) и (х,и), такими, что с(и,х) = с(х,и) = с(и, и).

Покажите, что максимальный поток в С' имеет ту же величину, что н в С. 261.2 Распространите свойства потока и определения на задачу с несколькими истоками и стоками. Покажите, что любой поток в сети с несколькими истоками и стоками соответствует потоку той же величины в сети с единственным истоком и стоком, получаемой путем добавления фикгивных истока и стока, и наоборот. 261.З Предположим, что транспортная сеть С = (К, Е) нарушает предположение о том, что в сети имеются пути в и- 1для всех вершин и е У. Пусть и представляет собой вершину, для которой такого пути в - и б нет. Покажите, что в С должен существовать максимальный поток 1, такой, что 1(и, и) = 1(и, и) = О для всех вершин и е У.

26.1.4 Пусть 1 является потоком в сети, и пусть о — действительное число. Скалярньгм произведением потока (зса1аг йочг ргобисГ), обозначаемым как о1, является функция, отображающая У х У на К и определенная следующим образом: (сг1)(и,и) = сг.1(и,и) . Докажите, что потоки в сети образуют выпуклое множеепгво, т.е. покажите, что если 7г и 1з являются потоками, то потоком является и сг гг + (1 — сг) Гз для всех гг из диапазона О < сг < 1. Сформулируйте задачу о максимальном потоке в виде задачи линейного програм- мирования. Глава 26 Задача о максимальном ломаке 753 26.1.6 У профессора двое детей, которые, к сожалению, терпеть не могут друг друга.

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

Покажите, как сформулировать задачу о возможности отправить детей в одну и ту же школу в виде задачи о максимальном потоке. 26.1.7 Предположим, что в дополнение к пропускным способностям ребер транспортная сеть имеет пропускные способности вершин, т.е. каждая вершина с имеет предел Цс), определяющий, какой величины поток может через нее проходить. Покажите, как преобразовать транспортную сеть С = (Ъ; Е) с пропускными способностями вершин в эквивалентную транспортную сеть С' = (Ъ", Е') без пропускных способностей вершин, такую, что максимальный поток в С' имеет ту же величину, что и максимальный поток в С. Сколько ребер и вершин входят в С'? 26.2.

Метод Форда-Фалкерсона В данном разделе представлен метод Форда-Фапкерсона для решения задачи о максимальном потоке. Мы называем его методом, а не алгоритмом, поскольку он допускает несколько реализаций с различным временем выполнения. Метод Форда — Фалкерсона базируется на трех важных идеях, которые выходят за рамки данного метода и применяются во многих потоковых алгоритмах и задачах. Это — остаточные сети, увеличивающие пути и разрезы.

Данные концепции лежат в основе важной теоремы о максимальном потоке и минимальном разрезе (теорема 26.6), которая определяет значение максимального потока через разрезы транспортной сети. В заключение данного раздела мы предложим одну конкретную реализацию метода Форда-Фапкерсона и проанализируем время ее выполнения.

Метод Форда-Фалкерсона итеративно увеличивает значение потока. Вначале поток обнуляется: Дн, с) = 0 для всех и, е е Ъ'. На каждой итерации величина потока в С увеличивается посредством поиска "увеличивающего пути" в связанной "остаточной сети" С1. Зная ребра увеличивающего пути в СГ, мы можем легко идентифицировать конкретные ребра в С, для которых можно изменить поток таким образом, что его величина увеличится. Хотя каждая итерация метода Форда-Фалкерсона увеличивает величину потока, мы увидим, что поток через конкретное ребро С может возрастать или уменьшаться; уменьшение потока через некоторые ребра может быть необходимым для того, чтобы позволить алгоритму переслать больший поток от истока к стоку.

Мы многократно увеличиваем Часть ЕЕ Аягариашм дла рааамм с графами 754 поток до тех пор, пока остаточная сеть не будет иметь ни одного увеличивающего пути. В теореме о максимальном потоке и минимальном разрезе будет показано, что по завершении данного процесса получается максимальный поток. РОкп-РБекекБОТ4-МетнОО (С, а, 1) 1 Инициализация потока 5 нулевым значением 2 и1й1е существует увеличивающий путь р в остаточной сети С7 3 увеличиваем поток 5 вдоль пути р 4 ге1цгп 5" Чтобы реализовать и проанализировать метод Форда — Фалкерсона, необходимо ввести несколько дополнительных концепций.

Остаточные сети с(и, о) — 5' (и, о), если (и, и) Е Е, с7(и,о) = 5(о,и), если (о,и) е Е, 0 в противном случае . (26.2) В силу нашего предположения о том, что из (и, о) Е Е вытекает (о, и) ф Е, к каждой упорядоченной паре вершин применим только один случай из (26.2). В качестве примера (26.2), если с(и,о) = 16 и 5(и, о) = 11, мы можем увеличить 5(и, о) на величину, не превышающую с7(и, о) = 6 единиц, прежде чем Интуитивно понятно, что если заданы некоторая транспортная сеть С и поток У, то остаточная сеть С7 — это сеть, состоящая из ребер с пропускными способностями, указывающими, как могут меняться потоки через ребра С.

Ребро транспортной сети может пропустить дополнительный поток, равный пропускной способности ребра минус поток, проходяший через это ребро. Если это значение положительно, мы помещаем такое ребро в С7 с "остаточной пропускной способностью*' с7(ц, о) = с(ц, о) — 5(и, о). Дополнительный поток могут пропустить только те ребра в С, которые входят в С5, ребра (и, о), поток через которые равен их пропускной способности, имеют с5(и, о) = 0 и не входят в С7. Однако остаточная сеть С7 может также включать ребра, не входящие в С.

Когда алгоритм работает с потоком с целью его увеличения, ему может потребоваться уменьшить поток в некотором конкретном ребре. Чтобы представить возможное уменьшение положительного потока 5(ц, с) в ребре в С, мы помещаем ребро (о, и) в С7 с остаточной пропускной способностью с7(о, и) = 5(п, о), т.е. ребро, которое может пропустить поток в направлении, обратном к (и, о), не больше потока, идущего по ребру (и, о). Эти обратные ребра в остаточной сети позволяют алгоритму пересылать обратно поток, уже переданный по ребру.

Пересылка в обратном направлении эквивалентна уменьшению потока в ребре, которое во многих алгоритмах является необходимой операцией. Говоря более формально, предположим, что у нас есть транспортная сеть С = (17, Е) с истоком з и стоком ~. Пусть в С имеется поток 5", и рассмотрим пару вершин и, о Е Ъ'. Определим остаточную нронуснную способность с7(и, о) как Глава 2б. Задача о максимтьяоч лояюкв (6) (в) (в) (г) Рнс. 26А. (а) транспортная сеть С и поток Г", показанные на рис.

26.1, (б). (6) Остаточная сеть Сг с выделенным штриловюй увеличиваюшнм путем р; его остаточная пропусююл способность равна с)(р) = сГ(сз,сз) = 4. Ребра с остаточной пропускной способностью, рваной О, такие как (ог, оз), не показаны (соглашение. мпсрому мы будем следовать в оставшейся части этого раздела). (в) Поток в С, полученный в результате увеличения вдоль пути р на его остаточную пропускную способность 4. Ребра, не несущие поток, такие как (сз, оз), помечены только пропускной способностью (еше одно соглашение, которому мы будем следовать).

(г) Остаточная сеть, поронденная потоком в (в). превысим ограничение пропускной способности ребра (и,и). Мы также хотим позволить алгоритму возвращать до 11 единиц потока назад от и к и, и следовательно, су(с,и) = 11. Для заданной транспортной сети С = ((Г, Е) и потока у остоточная сеть (гез(((па! пепчог(() С, порожденная потоком /, представляет собой граф Сг = (Ъ; Ег), где Ег = ((и, с) б (г х Ъ': сг(и, и) > О) (26.3) Иначе говоря, как и отмечалось выше, по каждому ребру остаточной сети, или остоточнану ребру, можно направить поток, больший О.

Характеристики

Список файлов книги