Алгоритмы - построение и анализ (1021735), страница 151
Текст из файла (страница 151)
Количество г'(и, и), которое может быть положительным, нулевым или отрицательным, называется потокам (йо)ч) из вершины и в вершину и. Величина (ча)пс) потока ~ определяется как И=~ ~У( и) (26.1) сер т.е. как суммарный поток, выходящий из источника (в данном случае Н обозначает величину потока, а не абсолютную величину или мощность). В задаче о максамальном потоке (шахппшп йосч ргоЫеш) дана некоторая транспортная сеть С с источником з и стоюм с, и необходимо найти поток максимальной величины. Перед тем как рассматривать пример задачи о потоке в сети, кратко проанализируем три свойства потока.
Ограничение пропускной способности предполагает, чтобы поток из одной вершины в другую не превышал заданную пропускную способность ребра. Антисимметричность введена для удобства обозначений и заключается в том, что поток из вершины и в вершину и противоположен потоку в обратном направлении. Свойство сохранения потока утверждает, что суммарный поток, выходящий из вершины, не являющейся источниюм или стоком, равен Глава 26. Задача о максимальном потоке 737 нулю.
Используя антисимметричность, можно записать свойство сохранения по- тока как У(и,и) = О для всех и й У вЂ” (а, 1), т.е. суммарный поток, входящий в вершину, отличную от источника и стока, равен О. Если в Е не присутствуют ни (и, и), ни (и, и), между вершинами и и и нет потока, и у (и, и) = Г" (и, и) = О. (В упражнении 26.1-! предлагается формально доказать это свойство.) Последнее наблюдение касается свойств, связанных с положительными потоками.
Суммарный положительный поток (соса! роз!сне йож), входящий в вершину и, задается выражением г (и, и). (26.2) Суммарный положительный поток, выходящий из некоторой вершины, определяется симметрично. Суммарным чистый поток (соса! пес йоч) в некоторой вершине равен разности суммарного положительного потока, выходящего из данной вершины, и суммарного положительного потока, входящего в нее.
Одна из интерпретаций свойства сохранения потока состоит в том, что для отличной от источника и стока вершины входящий в нее суммарный положительный поток должен быть равен выходящему суммарному положительному потоку. Свойство, что суммарный чистый поток в транзитной вершине должен быть равен О, часто нестрого формулируют как "входящий поток равен выходящему потоку". Пример потока С помощью транспортной сети можно моделировать задачу о грузовых перевозках, представленную на рис. 26.1а.
У компании 1лс1су Рис1с в Ванкувере есть фабрика (источник а), производящая хоккейные шайбы, а в Виннипеге — склад (сток с), где эти шайбы хранятся. Компания арендует места на грузовиках других фирм для доставки шайб с фабрики на склад. Поскольку грузовики ездят по определенным маршрутам (ребрам) между городами (вершинами) и имеют ограниченную грузоподъемность, компания Ьис1су РисЕ может перевозить не более с(и, и) ящиков в день между каждой парой городов и и и, как показано на рис. 26.1а. Компания Ьис!су Рис1с не может повлиять на маршруты и пропускную способность, т.е. она не может менять транспортную сеть, представленную на рис. 26.1а. Ее задача — определить, какое наибольшее юличество р ящиков в день можно отгружать, и затем производить именно такое количество, посюльку не имеет смысла производить шайб больше, чем можно отправить на склад.
Для 738 Часть Ч1. Алгоритмы для работы с графами юмпании не важно, сколько времени займет доставка конкретной шайбы с фабрики на склад, она заботится только о том, чтобы р ящиков в день отправлялось с фабрики и р ящиков в день прибывало на склад. На первый взгляд, вполне логично моделировать потоком в данной сети "поток" отгрузок, посюльку число яшиюв, оттружаемых ежедневно из одного города в другой, подчиняется ограничению пропускной способности. Кроме того, должно соблюдаться условие сохранения потока, поскольку в стационарном состоянии скорость ввоза шайб в некоторый промежуточный город должна быть равна скорости их вывоза.
В противном случае ящики станут накапливаться в промежуточных городах. Однако между отгрузками и потоками существует одно отличие. Компания 1ис1су РисЕ может отправлять шайбы из Эдмонтона в Калгари и одновременно из Калгари в Эдмонтон. Предположим, что 8 яшиюв в день оттружается из Эдмонтона (о1 на рис. 26.1) в Калгари (оз) и 3 ящика в день из Калгари в Эдмонтон. Как бы ни хотелось непосредственно представлять отгрузки потоками, мы не можем этого сделать. Согласно свойству антисимметричности, должно выполняться условие ,г (и, оз) = — г" (ез, е1 ), но это, очевидно, не так, если считать, что г" (оы оз) = 8, а У (ег, о1 ) = 3. Компания Ьиску РисЕ понимает, что бессмысленно отправлять 8 ящиюв в день из Эдмонтона в Калгари и 3 ящика из Калгари в Эдмонтон, если того же результата можно добиться, отгружая 5 ящиков из Эдмонтона в Калгари и 0 ящиков из Калгари в Эдмонтон (что потребует к тому же меньших затрат). Этот последний сценарий мы и представим потоком: Г" (оы оз) = 5, а 7" (оя, и1) = — 5.
По сути, 3 из 8 ящиков в день, отправляемые из о1 в оз, взаимно уничтожаются (сапсе1еб) с 3 ящиками в день, отправляемыми из ез в оп В общем случае взаимное уничтожение позволяет нам представить отгрузки между двумя городами потоком, который положителен не более чем вдоль одного из двух ребер, соединяющих соответствующие вершины. Таким образом, любую ситуацию, когда ящики перевозятся между двумя городами в обоих направлениях, можно привести с помощью взаимного уничтожения к эквивалентной ситуации, в которой ящики перевозятся толью в одном направлении — направлении положительного потока. По определенному таким образом потоку 7" нельзя восстановить, какими в действительности являются поставки.
Если известно, что г" (и, о) = 5, то это может быть как в случае, когда 5 единиц отправляется из и в о, так и в случае, югда 8 единиц отправляется из и в о, а 3 единицы из о в и. Обычно нас не будет интересовать, как в действительности организованы физические поставки, для любой пары вершин учитывается толью чистое пересылаемое количество. Если важно знать объемы действительных поставок, следует использовать другую модель, в которой сохраняется информация о поставках в обоих направлениях. Глава 26.
Задача о максимальном потоке 739 Взаимное уничтожение неявно будет присутствовать в рассматриваемых в данной главе алгоритмах. Предположим, что ребро (и,е) имеет величину потока ~(и,е). В процессе выполнения алгоритма мы можем увеличить поток вдоль ребра (е, и) на некоторую величину 6. С математической точки зрения, эта операция должна уменьшить г (и, е) на И, следовательно, можно считать, что эти 6 единиц взаимно уничтожаются с с~ единицами потока, который уже существует вдоль ребра (и, и). Сети с несколькими источниками и стоками В задаче о максимальном потоке может быть несколько источников и стоков.
Например, у компании 1лску Риса может быть тп фабрик (вы аз,...,в ) и п складов (~ы ~э,...,т„), как показано на рис. 26.2а„где приведен пример транспортной сети с пятью источниками и тремя стоками. К счастью, эта задача не сложнее„чем обычная задача о максимальном потоке. Задача определения максимального потока в сети с несколькими источниками и несколькими стоками сводится к обычной задаче о максимальном потоке. На рис. 26.26 показано, как сеть, представленную на рис. 26.2а, можно превратить в обычную транспортную сеть с одним источником и одним стоком. Для Рис. 26.2. Преобразование задачи о максимальном потоке с несколькими источниками и несколькими стоками к задаче с одним источником и одним стоком Часть Ч1. Алгоритмы для работы с графами 740 этого добавляется фиктивный источник (ацрегзоцгсе) в и ориентированные ребра (в, в,) с пропускной способностью с(в, в,) = со для каждого з = 1,2,..., т.
Точно так же создается новый фиктивный сток (зцргез(пк) 1 и добавляются ориентированные ребра (Ц,1) с с(Ц,1) = со для каждого 1 = 1,2,..., и. Ингуитивно понятно, что любой поток в сети на рис. 26.2а соответствует потоку в сети на рис. 26.26 и обратно. Единственный источник в просто обеспечивает поток любого требуемого объема к источникам в;, а единственный сток Ф аналогичным образом потребляет поток любого желаемого объема от множественных стоков 1ь В упражнении 26.1-3 предлагается формально доказать эквивалентность этих двух задач. Как работать с потоками Далее нам придется работать с функциями, подобными 1', аргументами которых являются две вершины транспортной сети.
В данной главе мы будем использовать неявное обозначение суммирования (1шр11сй зшшпабоп по1айоп), в котором один аргумент или оба могут представлять собой множество вершин, интерпретируя эту запись так, что указанное значение является суммой всех возможных способов замены аргументов их членами. Например, если Х и У вЂ” множества вершин, то г" (Х, У) = ,'~ ~,г" (х, у). хсх уеУ Тогда условие сохранения потока можно записать как г (и, У) = О для всех и Е У вЂ” (в,г). Для удобства мы также обычно будем опускать фигурные скобки при использовании неявного обозначения суммирования:например, в уравнении У (в, У вЂ” в) = г' (в, У) запись У вЂ” в обозначает множество У вЂ” (в). Использование неявного обозначения множеств обычно упрощает уравнения, описывающие потоки.
В следующей лемме, доказать которую читателю предлагается в качестве упражнения 26.1-4, формулируются основные тождества, связывающие потоки и множества. Лемма 26.1. Пусть С = (У,Е) — транспортная сеть, и г" — некоторый поток в сети С. Тогда справедливы следующие равенства. 1. Для всех Х С У г" (Х,Х) = О. 2. Для всех Х, У С У г" (Х, У) = — г' (У, Х). 3. Для всех Х, У, УСУ, таких что ХПУ = 9, г" (Х 0 У, Я) = г" (Х, Я)+г' (У, Я) и У(г, Х и У) = У(г, Х)+ У (г, У). В качестве примера работы с неявным обозначением суммирования, докажем, что значение потока равно суммарному потоку, входящему в сток; т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
