Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 124
Текст из файла (страница 124)
Рассмотрим сеть, изображенную на рис. !6.5. РЛЗДбЛ 16Л. Сети и потоки 697 (3.3) Ь вЂ” '— с Ф ф ~ф а '3 Ф' 4, (4,4) Рис. !б б Кажется, что у этой сети максимальный поток, потому что не сушествует ориентированного пути, по которому можно увеличить поток. Заметим, однако, что сеть на рис.
!6.6 имеет больший поток, и, фактически, он максимальный. (3,3) 9 4Ь а ,Й, ~Ф' о' б ~е ~0 (4,2) Риа /б.б Следует обратить внимание, что если поток из источника равен сумме пропускных способностей ребер, выходящих из источника, или поток, втекаюший в сток, равен сумме пропускных способностей ребер, входяших в сток, то поток максимальный. Однако, поток может быть максимальным и без удовлетворения какого-либо из этих признаков. Например, сеть на рис, 16.7 имеет максимальный поток. (1,1) ~ Ь вЂ” с г -Ф „ (2,2) Итак, как же находить максимальные в смысле потока сети? Для этого сформируем пути из а в 3, не обрашая внимания на направление ребер.
Такие пути назовем целями. Рассмотрим снова сеть с потоком, изображенную на рис. 16.5. Одним из таких путей является (8,6) (3,3) (9,6) а — Ь вЂ” с — 3. Очевидно, что нет возможности увеличить поток по этому пути, поскольку ребро из Ь в с наполнено до его пропускной способности. То же самое верно и для цепи (8,6) (5,3) (т,т] а -'-+ Ь -'~ е -'~ г.
Однако, при рассмотрении цепи (8,6) (5,3) (4,4) (5,3) (9,6) а — '- Ь вЂ” е — б -' с -~ 698 ГЛИНА тб. Сети видим: если увеличить поток на 2 для стрелок, имеющих то же самое направление, что и цепь, и уменьшить поток на 2 для стрелок, имеющих противоположное направление, то получим (8,8) (5,5) (4,2) (5,5) (9,8) а -' 6 -'- е ~'- д -'~ с -~ а, что увеличивает поток на 2.
Первый вопрос, который следовало бы задать: "Почему выбираем 22". Вполне очевидно, что поток желательно увеличить как можно больше. Но он не может превысить пропускную способность ни одного из заданных ребер. Именно по этой причине мы ограничены величиной 2. Кроме того, если ребро имеет направление, противоположное цепи, то нельзя уменьшить поток через это ребро более, чем на текущую величину потока через него, иначе получим отрицательный поток.
Поэтому, если бы не было других ограничений, то ограничило бы изменение потока до 4. Второй вопрос: "Как это влияет на сохранение потока?". Убедимся, что условие сохранения потока выполняется. Рассмотрим, например, изменение (8,8) (5,3) а — Ь -~ е на (8,8) (5,5) а -' Ь вЂ” е. Поток, выходящий из вершины Ь, увеличен на ту же самую величину, что и поток, входящий в вершину Ь. Поэтому чистый поток через 6 остается прежним. При изменении (5,3) (4,4) Ь вЂ” е -4( на (5,5) (4,2) 6-4 е — 4( поток из вершины 6 в вершину е увеличен на ту же величину, на которую уменьшен поток из вершины и' в вершину е, поэтому чистый поток в вершине е остался тем же.
Наконец, рассмотрим изменение (4,4) (5,3) е — Ы вЂ” с на (4,2) (5,5) е — д — с Поток из 4( в е уменьшен на ту же величину, на которую увеличен поток из 4( в с. Поэтому чистый поток и вершины д остался неизменным. Процесс увеличения потока в сети чрезвычайно прост. Формируем цепь из а в 2. Если возможно, то увеличиваем поток, определяя наибольшую величину, которую можно добавить к каждому из ребер, имеющих то же самое направление, что и цепь, чтобы поток не превысил пропускную способность, и которую можно вычесть из каждого ребра, имеющего противоположное направление, не РАздел 1б.
и сети и потоки 699 создавая отрицательный поток. Поскольку последнее ребро, входящее в з, имеет то же самое направление, что и цепь, то поток в з возрастает. Аналогично, ребро, выходящее из а, имеет то же самое направление, что и цепь, поэтому, как и ожидалось, поток из а возрастает. Так и должно было быть, потому что поток(а) = лоток(з). Потому что пропускная способность — конечная величина, а общая величина потока увеличивается, неизбежно наступает момент, когда наращивать поток далее нельзя.
Когда это происходит, получаем максимальный поток. До сих пор рассматривался способ увеличения уже существующего потока. А с какого потока начинать? Ответ прост. Следует начинать с нулевого потока, т.е. когда поток через каждое ребро равен О, а затем наращивать его. Теперь перейдем к изложению систематического алгоритма для нахождения максимального потока.
Каждой вершине поставим в соответствие упорядоченную пару. Первый элемент пары — предшествующая вершина в рассматриваемой цепи предназначена для того, чтобы можно было найти обратный путь. Второй элемент пары— резерв, т.е. величина, на которую можно увеличить поток на каждом ребре вдоль пути, если ориентация ребра совпадает с направлением цепи (такую ориентацию назовем правильной), или уменьшить поток, если ребро ориентировано неправильно.
Проще говоря, резерв заданной вершины равен максимальной величине, на которую поток вдоль цепи до этой вершины можно увеличить без нарушения самого потока. Рассмотрим также множество 5, содержащее все вершины, не задействованные при построении цепи в з. Если 5 окажется пустым, до того как будет достигнута вершина з, то больше не будет вершин, которые можно испытать на пути к ., поэтому нет иного пути в а и нет более возможности увеличить поток, значит поток максимален. Алгоритм (Форда-Фалкерсона) нахождения максимального потока (1) Установить предшественника каждой вершины и резерв равными символу — (непомечено). Вершина помечена, когда ее резерв не обозначен символом —.
Установить резерв вершины а равным оо, с тем чтобы она не ограничивала резерв других вершин. Положить 5 = (а). (2) Если 5 — пустое множество, то поток максимизирован. Если 5 не является пустым, то выбираем любой элемент нз 5 и удаляем его. Полагаем этот элемент равным и. (3) Если ш не помечена, (и, ш) является ребром и г'((и,ю)) < с((и, ш)). Положить резерв вершины ш равным минимуму величины с((и, ю)) — г" ((и, и)) и резерва вершины и. Установить предшественника вершины ш в и. Если и Ф з, добавить и в 5. (4) Если ш не помечена, (ш,и) является ребром и г"((и,ш)) > О. Положить резерв вершины ю равным минимуму из Г"((и,ю)) и резерва вершины и.
Установить предшественника вершины ш в и. Добавить ш во множество 5. (5) Если з помечена, то, используя функцию предшествования, вернуться в вершину а и для каждого ребра цепи добавить резерв вершины з к потоку каждого правильно ориентированного ребра, и вычесть резерв з из потока каждого неправильно ориентированного ребра. Вернуться к шагу 1.
(6) Вернуться к шагу 2. 700 ГЛАНА 76. Свеи Требуется еще доказать, что алгоритм действительно определяет максимальный поток, но сначала посмотрим, как он работает. ПРИМЕР 16.13. Найдем максимальный поток для сети, изображенной на рис. 16.8.
Г Г' ° 6 б 2 Рис. 16.8 На шаге 1 для каждой вершины устанавливаем предшественника и резерв равными символу —, для вершины а устанавливаем резерв, равный оо, и полагаем Я = (а). После чего получаем сеть, изображенную на рис. 16.9. На шаге 2 проверяем, не пусто ли множество Я, и выбираем из него вершину а. На шаге 3 полагаем резерв вершины Ь равным ппп(7, оо) = 7 и устанавливаем вершину а в качестве предшественника вершины Ь. Помещаем вершину Ь во множество Я. Устанавливаем резерв вершины а равным пйп(6, со) = 6 и устанавливаем вершину а в качестве предшественника вершины с(. Помещаем вершину а во множество Я. Шаги 4 и 5 не применяем, поэтому возвращаемся к шагу 2.
Проверяем, не является ли множество Я пустым, и выбираем из него вершину, например, Ь. Теперь множество Я содержит только вершину а. На шаге 3 полагаем резерв вершины с равным ппп(3,7) = 3 и устанавливаем вершину Ь в качестве предшественника вершины с. Помещаем вершину с во множество Я, так что Я = (с,г(). Опять шаги 4 и 5 не применяем и возвращаемся к шагу 2. Проверяем, не является ли множество Я пустым, и выбираем из Я вершину, например, с. Множество Я опять содержит только вершину Н. На шаге 3 полагаем резерв вершины 3 равным ппп(3,5) = 3 и устанавливаем вершину с в качестве предшественника вершины 3. Не помещаем 3 во множество Я. На шаге 4 следует пометить вершину Ы, но она уже помечена.
На шаге 5 видим, что вершина 3 уже помечена, и, используя функцию пред- шествования, находим цепь (7,0) (3,0) (5,0) а -~ Ь -~ с -~ Добавляя 3 (резерв вершины 3) к потоку каждого ребра, получаем (7,3) (3,3) (5,3) а-~Ь-с — + 3, что дает сеть, изображенную на рис. 16.10. РАЗДЕЛ та. П Сегпи и попюки 701 Теперь возвращаемся к шагу 1, где переустанавливаем метки и предшественников и полагаем Я = 1а). На шаге 2 выбираем вершину а из множества Я. На шаге 3 устанавливаем резерв вершины Ь равным ш!п(оо,7 — 3) = 4 и устанавливаем а в качестве предшественника вершины Ь.
Помещаем вершину Ь во множество Я. Полагаем также резерв вершины 41 равным 6 и устанавливаем вершину а в качестве предшественника вершины 4(. Помешаем вершину Н во множество Я. Шаги 4 и 5 не применяем, поэтому возвращаемся к шагу 2. Выбираем вершину Ь из множества Я. Поскольку поток из Ь в с равен пропускной способности из Ь в с, то вершину с не помечаем. Выбираем вершину й из множества Я и продолжаем процесс, после чего получаем цепь (6,0) (2,0) а-'Н вЂ” 'з и, добавляя 2 (резерв вершины 2) к потоку каждого ребра, получаем цепь (6,2) (2,2) а †'+ 6( — 2.
Текушая ситуация изображена на рис, 16.!1. Г(~ Снова возвращаемся к шагу 1 и повторяем процесс, пока не получим цепь (6,2) (2,0) (5,3) а-'~Ы-~с-~ з. Добавляя 2 (резерв вершины 2) к потоку каждого ребра, получаем (6Л) (2,2) (5,5) а — ~Н вЂ” ~с — +з. Ситуация изображена на рис. 16.12. 702 ГЛАВА тб. Сегли о'. Гз,з> Г Г'"', (4,4) б * ( ,2) (а,4) (2,2) р(бс Гб 12 Возвращаемся к шагу 1, переустанавливаем метки предшественника и полагаем Я = (а). На шаге 2 выбираем вершину а из множества Я. Как и ранее, на шаге 3 полагаем резерв вершины Ь равным 4 и устанавливаем вершину а в качестве предшественника вершины Ь. Помещаем вершину Ь во множество Я.
Устанавливаем также резерв вершины (( равным 6 — 4 = 2 и помешаем вершину (1 во множество Я. Возвращаемся к шагу 2. Выбираем вершину Ь из множества Я. Поскольку поток из вершины Ь в вершину с равен пропускной способности из Ь в с, пометить с нельзя, поэтому, в конце концов, возвращаемся к шагу 2. Выбираем вершину 4( из множества Я, Поскольку поток из вершины (( в вершину с и вершину г равен их пропускным способностям, нельзя помечать с и з. Опять возвращаемся к шагу 2, но множество 5 пусто. Процесс закончен. Окончательный поток изображен на рис.16.13. «~- Яэ) ~ф. Ф с(-,-) а(- ) ~~ -В~ (4.4 6 — *(.:) (а,а) (2,2) Рис. !б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
