Алгоритмы - построение и анализ (1021735), страница 152
Текст из файла (страница 152)
(26.3) ~Л = У(У1) Глава 26. Задача о максимальном потоке 741 !У! = (по определению) (согласно лемме 26.1, часть 3) (согласно лемме 26.1, часть 1) (согласно лемме 26.1, часть 2) (согласно лемме 26.1, часть 3) (согласно свойству сохранения потока). Далее в данной главе мы обобщим данный результат (лемма 26.5). Упражнения Используя определение потока, докажите, что если (и, с) ф Е и (о, и) ф ф Е, то г" (и, с) = г" (о, и) = О. Докажите, что для любой вершины о, отличной от источника и стока, суммарный положительный поток, входящий в о, должен быть равен суммарному положительному потоку, выходящему из э. 26.1-1.
26.1-2. Распространите определение и свойства потока на случай задачи с несколькими источниками и несколькими стоками. Покажите, что любой поток в транспортной сети с несколькими источниками и несколькими стоками соответствует некоторому потоку идентичной величины в сети с единственным источником и единственным стоком, полученной путем добавления фиктивного источника и фиктивного стока, и наоборот.
26.1-3. 26.1-4. 26.1-5. Докажите лемму 26.1. Для транспортной сети С = (У, Е) и потока Г, показанных на рис. 26.16, найдите пару подмножеств Х, У С У, для которых 1 (Х, У) = -Г(У— — Х,У). Затем найдите пару подмножеств Х,У С К, для которых г(Х, У) ф — Г(У вЂ” Х, У). Пусть дана транспортная сеть С = (У, Е), и пусть 11 и Гз — функции, отображающие У х У в К.
Суммой потоков Г1 + Гз является функция, 26.1-6. Интуитивно мы ожидаем, что зто свойство справедливо. Согласно условию сохранения потока, все вершины, отличные от источника и стока, имеют одинаковые величины входящего и выходящего положительного потока. Источник по определению имеет суммарный чистый поток, больший О; т.е. из источника выходит больший положительный поток, чем входит в него. Симметрично, сток является единственной вершиной, которая может иметь суммарный чистый поток, меньший О; т.е. в сток входит больший положительный поток, чем выходит из него. Формальное доказательство выглядит следующим образом: Часть Ч1. Алгоритмы для работы с графами 742 отображающая 1" х г' в а и определяемая как (Л+,гз) (и,е) = Л (и,е) + гз(и,с) (26.4) для всех и, о ЕУ. Если 1з и 5 — потоки в С, то каким из трех свойств потоков удовлетворяет сумма потоков 71 + 5, и какие из них могут нарушаться? 26.1-7.
Пусть 7" — поток в сети, а а — некоторое действительное число. Произведение потока на скаляр (зса1аг йоч~ ргобцс1)„обозначаемое как о7',— это функция, отображающая Ъ" х ~' в а, такая что (а,1 ) (и, е) = а 1 (и, с) . Докажите, что потоки в сети образуют выпуклое множество (солчех зе1), т е. покажите, что если 71 и 7з являются потоками, то а(1+ (1 — а) 7з также является потоком для любых О < о < 1. 26.1-8. Сформулируйте задачу о максимальном потоке в виде задачи линейного программирования. 26.1-9.
У профессора двое детей, которые, к сожалению, терпеть не могут друг друга. Проблема настолько серьезна, что они не только не хотят вместе ходить в школу, но каждый даже отказывается заходить в квартал, в котором в этот день побывал другой. При этом они допускают, что их пути могут пересекаться на углу того или иного квартала. К счастью, и дом профессора, и школа расположены на углах кварталов, однако профессор не уверен, возможно ли отправить обоих детей в одну школу. У профессора есть карта города.
Покажите, как сформулировать задачу о возможности отправить детей в одну и ту же школу в виде задачи о максимальном потоке. 26.2 Метод Форда-Фалкерсона В данном разделе представлен метод Форда-Фалкерсона для решения задачи о максимальном потоке. Мы называем его методом, а не алгоритмом, поскольку он допускает несколько реализаций с различным временем выполнения. Метод Форда-Фалкерсона базируется на трех важных концепциях, которые выходят за рамки данного метода и применяются во многих потоковых алгоритмах и задачах. Это — остаточные сети, увеличивающие пути и разрезы. Данные концепции лежат в основе важной теоремы о максимальном потоке и минимальном разрезе (теорема 26.7), которая определяет значение максимального потока с помощью разрезов транспортной сети.
В заключение данного раздела мы предложим одну Глава 26. Задача о максимальном потоке 743 юнкретную реализацию метода Форда-Фалкерсона и проанализируем время ее выполнения. Метод Форда-Фалкерсона является итеративным. Вначале величине потока присваивается значение 0: Г' (и,и) = 0 для всех и, и 6 У. На каждой итерации величина потока увеличивается посредством поиска "увеличивающего пути" (т.е. некого пути от источника а к стоку г, вдоль юторого можно послать больший поток) и последующего увеличения потока. Зтот процесс повторяется до тех пор, пока уже невозможно отыскать увеличивающий путь. В теореме о максимальном потоке и минимальном разрезе будет показано, что по завершении данного процесса получается максимальный поток.
РОкп Р~л.кекзОх МетнОО(С, в,1) 1 Задаем начальное значение потока у равным 0 2 иЫ!е (Пока) существует увеличивающий путь р 3 йо увеличиваем поток у вдоль пути р 4 гетигп Г' Остаточные сети Интуитивно понятно, что если заданы некоторая транспортная сеть и поток, то остаточная сеть — это сеть, состоящая из ребер, допускающих увеличение потока. Более строго, пусть задана транспортная сеть С = (Ъ; Е) с источником а и стоком 1. Пусть 1' — неюторый поток в С. Рассмотрим пару вершин и, и Е Е Ъ'. Величина дополнительного потока, который мы можем направить из и в и, не превысив пропускную способность с (и, и), является остаточной пропускной способностью (гезЫпа! сарасйу) ребра (и, и), и задается формулой су (и, и) = с (и, и) — г (и, и) .
(26.5) Еу = ((и, и) 6 У х Ъ": сГ (и, и) ) 0). Например, если с(и,и) = 16 и у (и,и) = 11, то у (и,и) можно увеличить на су (и, и) = 6, не нарушив ограничение пропускной способности для ребра (и, и). Когда поток у (и, и) отрицателен, остаточная пропускная способность су (и, и) больше, чем пропускная способность с(и, и). Так, если с(и, и) = 16 н,г" (и, и) = = — 4, то остаточная пропускная способность су (и, и) = 20. Зту ситуацию можно интерпретировать следующим образом: существует поток величиной 4 единицы из и в и, юторый можно аннулировать, направив 4 единицы потока из и в и. Затем можно направить еще 16 единиц из и в и, не нарушив ограничение пропускной способности для ребра (и, и). Таким образом, начиная с потока у (и, и) = — 4, мы направили дополнительные 20 единиц потока, прежде чем достигли ограничения пропускной способности.
Для заданной транспортной сети С = (1г, Е) и потока у, остаточной сетью (гез16па1 пепчог1с) в С, порожденной потоюм г", является сеть Су = (г', Еу), где Часть Ч1. Алгоритмы для работы с графами 744 а) Рис. 26.3. а) Транспортная сеть С и поток 1', представленные на рис. 26.1б. 6) Остаточная сеть Сг с выделенным увеличивающим путем; его остаточная пропускная способность равна 4.
в) Поток в сети С, полученный в результате увеличения потока вдоль луги р на величину его остаточной пропускной способности 4. г) Остаточная сеть, порожденная потоком, показанным в части в) Таким образом, как и отмечалось выше, по каждому ребру остаточной сети, или остаточному ребру (гезкЬи! едйе), можно направить поток, больший О. На рис. 26.3а воспроизведены транспортная сеть С и поток )', представленные на рис.
26.1б, а на рис. 26.3б показана соответствующая остаточная сеть Су. Ребрами Еу являются или ребра Е, или обратные нм. Если у (и, и) < с(и,и) для некоторого ребра (и, и) Е Е, то су (и, и) = с (и, и) — Г" (и, о) > О и (и, и) Е Е1. Если Г'(и,и) > О для некоторого ребра (и, и) е Е, то у (и,и) < О. В таком случае су (и,и) = с(и,и) — г"(и,и) > О и, следовательно, (и,и) е Еу. Если в исходной сети нет ни ребра (и, и), ни (и,и), то с (и, и) = с (и,и) = О, г"(и, и) = г"(и,и) = = О (согласно результатам упражнения 26.1-1), и су (и, и) = су (и,и) = О.
Таким образом, можно сделать вывод, что ребро (и, и) может оказаться в остаточной сети только в том случае, если хотя бы одно из ребер (и, и) или (и, и) присутствует в исходной транспортной сети, поэтому (Еу! < 2 )Е~. Обратите внимание, что остаточная сеть Су является транспортной сетью со значениями пропускных способностей, заданными су.
Следующая лемма показывает, как поток в остаточной сети связан с потоком в исходной транспортной сети. Лемма 26.2. Пусть С = (К Е) — транспортная сеть с источником з и стоком 1, а г — поток в С. Пусть Су — остаточная сеть в С, порожденная потоком у, а г"'— Глава 26. Задача о максимальном потоке 745 поток в С т. Тогда сумма потоков у + у', определяемая уравнением (26.4), является потоком в С, и величина этого потока равна (~+ У'! = !Д + ~У'~ Доказалзельсзлво. Необходимо проверить, выполняются ли ограничения антисимы«триччости, пропускной способности и сохранения потока. Для подтверждения антисимметричности заметим, что для всех и, о Е '«', справедливо ( г" + г ) (и, о) = у (и, о) + у (и, о) = = — у(о,и) — у'(о,и) = = — (у (о, и) + г"' (о, и) ) = = — (Г+ ~') (о,и) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
