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

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

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

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 У, Я) = г" (Х, Я)+г' (У, Я) и У(г, Х и У) = У(г, Х)+ У (г, У). В качестве примера работы с неявным обозначением суммирования, докажем, что значение потока равно суммарному потоку, входящему в сток; т.е. (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. У профессора двое детей, которые, к сожалению, терпеть не могут друг друга. Проблема настолько серьезна, что они не только не хотят вместе ходить в школу, но каждый даже отказывается заходить в квартал, в котором в этот день побывал другой. При этом они допускают, что их пути могут пересекаться на углу того или иного квартала. К счастью, и дом профессора, и школа расположены на углах кварталов, однако профессор не уверен, возможно ли отправить обоих детей в одну школу.

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

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