Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 156
Текст из файла (страница 156)
26.2-7. Докажите лемму 26.3. 26.2-8. Покажите, что максимальный поток в сети О = (У, Е) всегда можно найти с помощью последовательности не более чем из ~Е~ увеличивающих путей. (Указание: считая, что максимальный поток известен, покажите, как следует выбирать пути.) 26.2-9. Запасиег связиослги (едйе соппес11т11у) неориентированного графа назовем минимальное число ребер 1г, которые необходимо удалить, чтобы разъединить граф.
Например, запас связности дерева равен 1, а запас связности циклической цепи вершин равен 2. Покажите, как определить запас связности неориентированного графа С = (У, Е) с помощью алгоритма максимального потока не более чем для Щ транспортных сетей, каждая из которых содержит О (У) вершин и О (Е) ребер. 26.2-10. Предположим, что транспортная сеть С = (У, Е) содержит симметричные ребра, т.е. (и, п) е Е тогда и только тогда, когда (е, и) е Е. Покажите, что алгоритм Эдмондса-Карпа завершается после не более чем ЩИЕ~у'4 итераций.
(Указание: для произвольного ребра (и, и) проследите, как меняются б(а,и) и б(п,т) между последовательными моментами, когда ребро (и, е) становится критическим.) 26.3 Максимальное паросочетание Некоторые комбинаторные задачи можно легко свести к задачам поиска максимального потока. Одной из таких задач является задача определения максимального потока в сети с несколькими источниками и стоками, описанная в разделе 26.1 Существуют другие комбинаторные задачи, которые на первый взгляд имеют мало общего с транспортными сетями, однако могут быль сведены к задачам поиска максимального потока.
В данном разделе рассматривается одна из подобных задач: поиск максимального паросочетания в двудольном графе (см. раздел Б.4). Чтобы решить данную задачу, мы воспользуемся свойством полноты, обеспечиваемым методом Форда-Фалкерсона. Мы также покажем, что с помощью метода Форда-Фалкерсона можно за время О (У Е) решить задачу поиска максимального паросочетания в двудольном графе С = (У, Е). Глава 26. Задача о максимальном потоке Задача поиска максимального паросочетания в двудольном графе Пусп дан неориентированный граф С = (К Е). Паросочеюиинием (ша~с)зшй) называется подмножество ребер М С Е, такое что для всех вершин е е У в М содержится не более одного ребра, инцидентного с. Мы говорим, что вершина с е У является связанной (ша~сЬед) паросочетанием М, если в М есть ребро, инцидентное э; в противном случае вершина о называется открытой (цпша1сЬед).
Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочегание М, что для любого паросочетания М' (М) > ~М'). В данном разделе мы ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества У = Ь 0 гь, где Ь и В не пересекаются, и все ребра из Е проходят между Ь и В. Далее мы предполагаем, что каждая вершина из 1' имеет по крайней мере одно инцидентное ребро. Иллюстрация понятия паросочетания показана на рис. 26.7.
Задача поиска максимального паросочетания в двудольном графе имеет множество практических приложений. В качестве примера можно рассмотреть паросочетание множества машин Ь и множества задач гс, которые должны выполняться одновременно. Наличие в Е ребра (и, с) означает, что машина и е Ь может выполнять задачу ю Е В.
Максимальное паросочетание обеспечивает максимальную загрузку машин. б) б) Рис. 26.7. Двудольный граф С = Я Е) с разбиением вершин У = Ь 0 В. а) Паросочетание с мощностью 2. б) Максимальное паросочетание с мощностью 3. Часть Ч!. Алгоритмы для работы с графами 758 Поиск максимального наросочетания в двудольном графе С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентнрованном двудольном графе С = 1Ъ;Е) за время, полиномиально зависящее от Щ и 1Е).
Проблема состоит в том, чтобы построить транспортную сеть, потоки в которой соответствуют паросочетаниям, как показано на рис. 26.8. Определим для заданного двудольного графа С соответствующую транспортную сеть С' = (Г, Е') следующим образом. Возьмем в качестве источника з и стока 1 новые вершины, не входящие в У, и пусть Ъ" = $' О (з, г). Если разбиение вершин в графе С задано как 1г = Ь о В, ориентированными ребрами С' будут ребра Е, направленные из Ь в тт, а также 1Ц новых ребер Е' = Цз, и): и Е .Ц 0 ((и, и): и Е Ь, и Е тт и (и, и) Е Е) О 1(и, 1): и Е тт) .
Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность. Поскольку каждая вершина из множества вершин Ъ" имеет по крайней мере одно инцидентное ребро, 1Е) > )Ъ")/2. Таким образом, 1Е! < ~Е'~ = = (Е(+ (Ц < 3)Е), так что )Е'~ = 9 (Е). б) Рнс. 26.8. Двудольный граф (а) н соответствующая ему транспортная сеть (б). Выделенные ребра обеспечивают максимальный поток н определяют максимальное паросочетанне Следующая лемма показывает, что паросочетание в С непосредственно соответствует некоторому потоку в соответствующей транспортной сети С'. Поток г" в транспортной сети С = (К Е) называется нелочисленньии (1лтейег-ча)иед), если значения Г" (и, и) целые для всех (и, и) Е Ъ' х У.
Лемма 26.10. Пусть С = 1'1г, Е) — двудольный граф с разбиением вершин У = = Ь 0 тт, и пусть С' = (Г, Е') — соответствующая ему транспортная сеть. Если 759 Глава 26. Задача о максимальном потоке М вЂ” паросочетание в С, то существует целочисленный поток г' в С', величина которого Щ = (М(. Справедливо и обратное утверждение: если ~ — целочисленный поток в С', то в С существует паросочетание М с мощностью )М! = )Д. Доказаюиельство. Покажем сначала, что паросочетанию М в графе С соответствует некоторый целочисленный поток Г" в сети С'.
Определим Г следующим образом. Если (и,е) Е М, то Г" (з,и) = Г" (и,о) = Г" (е,1) = 1 и Г" (и,з) = Г" (е,и) = Г" (1,п) = -1. Для всех остальных ребер (и,о) Е Е' определим Г" (и, о) = О. Нетрудно убедиться, что г" обладает свойством антисимметричности, удовлетворяет ограничениям пропускной способности и сохранения потока. Интуитивно понятно, что каждое ребро (и, о) Е М соответствует единице потока в С', проходящего по маршруту а — и ~ о — 8.
Кроме того, пути, порожденные ребрами из М, представляют собой непересекающиеся множества, не считая а и т. Чистый поток через разрез (Ь О (а),ВО (8)) равен (М); следовательно, согласно лемме 2б.5, величина потока равна (Я = (М!. Чтобы доказать обратное, предположим, что г" — некоторый целочисленный поток в С', и пусть М = ((и, о): и е Ь, е е В и г (и, о) ) О) . Каждая вершина и Е Ь имеет только одно входящее ребро, а именно (з, и), и его пропускная способность равна 1. Следовательно, в каждую вершину и Е Ь входит не более одной единицы положительного потока, и если она действительно входит, то из нее должна также выходить одна единица положительного потока согласно свойству сохранения потока. Более того, поскольку Г' — целочисленный поток, для каждой вершины и Е Ь одна единица потока может входить не более чем по одному ребру и выходить не более чем по одному ребру.
Таким образом, одна единица положительного потока входит в и тогда и только тогда, когда существует в точности одна вершина не В, такая что г" (и, и) = 1, и из каждой вершины ие ь выходит не более одного ребра, несущего положительный поток. Симметричные рассуждения применимы для каждой вершины о Е Я. Следовательно, М является паросочетанием. Чтобы показать, что )М( = Щ, заметим, что 1 (а, и) = 1 для каждой связанной вершины и Е Ь, и Г" (и, о) = О для каждого ребра (и, о) ŠŠ— М. Следовательно, ~М~ = Г (Ь, В) = Г" (Ь, У') — Г (Ы,) — Г" (Ь, а) — 1 (Ь, 1) согласно лемме 2б.!.
Приведенное выражение можно значительно упростить. Из свойства сохранения потока следует, что г (Ь, Г) = О; из леммы 26.1 следует, что г" (Ы,) = О; согласно свойству антисимметричности, -г" (Ь, а) = г" (а, Ь); и поскольку нет ребер, Часть Ч1. Алгоритмы для работы с графами 760 ведущих из Ь к т, 2" (Ь, 1) = О. Таким образом, (поскольку все ребра, выходящие из а, идут в Ь) (согласно определению Щ). На основании леммы 26.10 можно сделать вывод, что максимальное паросочетание в двудольном графе С соответствует максимальному потоку в соответствующей ему транспортной сети С', следовательно, можно находить максимальное паросочетание в С с помощью алгоритма поиска максимального потока в С'. Единственной проблемой в данных рассуждениях является то, что алгоритм поиска максимального потока может вернуть такой поток в С', в котором некоторое значение 1 (и, о) оказывается нецелым, несмотря на то, что величина Щ должна быть целой.
Следующая теорема показывает, что такая проблема не может возникнуть при использовании метода Форда-Фалкерсона. Теорема 26.11 (Теорема о целочисленности). Если функция пропускной способности с принимает только целые значения, то максимальный поток 1', полученный с помощью метода Форда-Фалкерсона, обладает тем свойством, что значение потока ~Я является целочисленным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
