Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 165
Текст из файла (страница 165)
Это одна из простейших задач, возникающих в транспортных сетях, и, как будет показано в данной главе, существуют эффективные алгоритмы ее решения. Более того, основные методы„используемые в алгоритмах решения задач о максимальном потоке, можно применять для решения других задач, связанных с транспортными сетями. В данной главе предлагается два общих метода решения задачи о максимальном потоке. В разделе 26.1 формализуются понятия транспортных сетей и потоков, а также дается формальное определение задачи о максимальном потоке. В разделе 26.2 описывается классический метод Форда-Фалкерсона ~рогдгнйсегзоп) для поиска максимального потока. В качестве приложения данного метода в разделе 26.3 осуществляется поиск максимального паросочегания в неори- 7лб Часть Рй Алгоритмы для рабаты с графами ентированном двудольном графе.
В разделе 26.4 описывается метод "проталкивания предпотока" ("рпвЬ-ге1аЬе!"), который лежит в основе многих наиболее быстрых алгоритмов для решения задач в транспортных сетях. В разделе 26.5 рассматривается еще один алгоритм, время работы юторого составляет О(!7а). Хотя он и не является самым быстрым известным алгоритмом, зато позволяет проиллюстрировать некоторые методы, используемые в асимптотически более быстрых алгоритмах, и на практике является достаточно эффективным.
26.1. Транспортные сети В данном разделе мы дадим определение транспортных сетей в терминах теории графов, обсудим их свойства, дадим точное определение задачи о максимальном потоке, а также введем некие полезные обозначения. Транспортные сети и потоки Трансяоргяяая сеть (Вотч пениог)г) С = ((7, Е) представляет собой ориентированный граф„в котором каждое ребро (и, и) е Е имеет неотрицательную пропускную сяособяослть (сарае!(у) с(и, и) > О.
Далее мы потребуем, чтобы в случае, если Е содержит ребро (и,и), обратного ребра (и,и) не было (вскоре мы увидим, как обойти это ограничение). Если (и,и) ф Е, то для удобства определим с(и,и) = О, а также запретим петли. В транспортной сети выделяются две вершины: асяюк (вопгсе) в и сток (а(п)с) 1. Для удобства предполагается, что каждая вершина лежит на неком пути от истока к стоку, т.е. для любой вершины и 6 Ъ' транспортная сеть содержит путь л и Ф. Таким образом, граф является связным и, посюльку каждая вершина, отличная от а, содержит как минимум одно входящее ребро, (Е) > ٠— 1.
На рис. 26.1 показан пример транспортной сети. Эдмонтон Саска тук гг Ванкувер ф т Т»,) д» " 0 Виннипег (.т )з~бл Калп|ри Регина (а) Рис. 26.1. (а) Транспортная сеть С = ()г, Е) для задачи о грузовых перевозках компании ьпсйу Рпс)с. Истоком л является фабрика в Ванкувере, а стоком à — склад в Виннипеге. Шайбы доставляются через промежуточные города, но за день из города и в ирод е можно стпратпь только с(и, е) ягпиюв. На рисунке указана пропускная способность кткдого ребра сети.
(б) Поток 7" в транспортной сети С со значением )Д = 19. Кткдое ребро (и, о) имеет метку 7'(н, о)/с(н, о) (косая черта используется талью для того, чтобы отделить поток ст пропускной способности, и не обозначает деление). Глава лд задача о максимальном потоке 149 Теперь мы готовы дать более формальное определение потоков. Пусть С = (у; Е) — транспортная сеть с функцией пропускной способности с. Пусть в является истоком, а 1 — стоком. Потоком (бок) в С является действительная функция ~: Ъ" х 'у' -+ Ж, удовлетворяющая следующим двум условиям.
Ограничение пропускной способности. Для всех и, и е Ъ' должно выполняться О < г"(и,и) < с(и,и). Сохранение потока. Для всех и б ь' — (в,1) должно выполняться 1(и, и) = ~~~ 1(и, и) . ояк Когда (и, и) 1е Е, потока из и в и быть не может, так что г" (и, и) = О. Неотрицательную величину )'(и, и) мы называем потоком из вершины и в вершину и. Величина (уа1ие) ~Д потока ~ определяется как (26.1) пеУ т.е.
как суммарный поток, выходящий из истока, минус входящий в него. (Здесь запись ( ~ означает величину потока, а не абсолютное значение нли мощность.) Обычно транспортная сеть не имеет ребер, входящих в исток, и поток в исток, задаваемый суммой 2 „У ((и, в), равен О. Однако мы включаем его, поскольку позже в этой главе при рассмотрении остаточных сетей потоки в исток станут важными. В задаче о максимальном потоке (шахппшп Оочч ргоЫеш) дана некоторая транспортная сеть С с истоком в и стоком 1, и необходимо найти поток максимальной величины. Перед тем как рассматривать пример задачи о потоке в сети, кратко проанализируем определение потока и два его свойства.
Ограничение пропускной способности просто гласит, что поток из одной вершины в другую должен быть неотрицательным и не должен превышать заданную пропускную способность ребра. Свойство сохранения потока утверждает, что суммарный поток, входящий в вершину, не являющуюся истоком или стоком, должен быть равен суммарному выходящему потоку, т.е., иначе говоря, что в вершину "втекает", то нз нее тут же и "вытекает". Пример потока С помощью транспортной сети можно моделировать задачу о грузовых перевозках, представленную на рис.
26.1,(а). У компании 1.иску Риск в Ванкувере есть фабрика (исток в), производящая хоккейные шайбы, а в Виннипеге — есть склад (сток 1), где эти шайбы хранятся. Компания арендует места на грузовиках других фирм для доставки шайб с фабрики на склад. Поскольку грузовики ездят по определенным маршрутам (ребрам) между городами (вершинами) и имеют ограниченную грузоподъемность, компания 1.иску Риск может перевозить не более с(и, и) ящиков в день между каждой парой городов и н и, как показано Часть 17. Аяяоритмм для рабомм с гра4ами 750 ; тэ~ Е (эае 14 (в) Рис. 16Д. Преобразование сети с антипараллельными ребрами в эквивалентную сеть без таковых. (а) Транспортная сеть, содермашая как ребро (ем ьз), так и ребро (ез, оз). (б) Эквивалентная сеп беэ антипараялельных ребер.
Добавлена новая вершина о', а ребро (ез, оз) заменено парой ребер (еы о') и (е', ез) с одной и той ме пропускной способностью (ез, ез). на рис. 26.1,(а). Компания Ьпску Риск не может повлиять на маршруты и пропускную способность, т.е. не может менять транспортную сеть, представленную на рис.
26.1,(а). Ее задача — определить, какое наибольшее количество р ящиков в день можно отгружать, и затем производить именно такое количество, поскольку не имеет смысла производить шайб больше, чем можно отправить на склад. Для компании не важно, сколько времени займет доставка конкретной шайбы с фабрики на склад, она заботится только о том, чтобы р ящиков в день отправлялось с фабрики и р ящиков в день прибывало на склад. Можно смоделировать потоком в данной сети "поток" отгрузок, поскольку число ящиков, отгружаемых ежедневно из одного города в другой, подчиняется ограничению пропускной способности. Кроме того, должно соблюдаться условие сохранения потока, поскольку в стационарном состоянии скорость ввоза шайб в некоторый промежуточный город должна быть равна скорости их вывоза.
В противном случае ящики станут накапливаться в промежуточных городах. Моделирование задач с антипараллельными ребрами Предположим, что фирма-перевозчик предлагает 1лзску Рис11 перевозку десяти ящиков в грузовике, идущем из Эдмонтона в Калгари. Представляется естественным добавить зту возможность в наш пример и получить транспортную сеть, показанную на рис. 26.2,(а).
Однако здесь возникает одна проблема: зта сеть нарушает исходное предположение о том, что если (и1, пз) б Е, то (пз, пз) ф Е. Два ребра, (и1, пз) и (пз, пг), называются аытилараллельными (апйрага11е!). Таким образом, если мы хотим моделировать задачу о потоке при наличии антипараллельных ребер, сеть следует преобразовать в эквивалентную, не содержащую антипараллельных ребер. На рис.
26.2, (б) показана такая эквивалентная сеть. Мы выбираем одно из двух антипараллельных ребер, в данном случае ребро (пы пз), и разбиваем его, добавляя новую вершину зУ и заменяя ребро (п1, пз) парой ребер (пз, и') и (и', пз). Мы также устанавливаем пропускную способность обоих новых ребер равной пропускной способности исходного ребра. Полученная в результате сеть удовлетворяет свойству, согласно которому при наличии некоторого ребра в сети встречное ребро в ией должно отсутствовать. В упр. 26.1.1 требует- Глаза Зй Задача о маясииальлаи лотояе 751 ся доказать, что полученная в результате описанных действий сеть эквивалентна исходной. Таким образом, как видим, реальные задачи о потоках могут быть более естественно смоделированы сетями с антипараллельными ребрами. Однако поскольку более удобным оказывается запрет на антипараллельные ребра, описанная процедура дает нам простой способ преобразовать сеть с антнпараллельными ребрами в эквивалентную сеть без таювых.
Сети с несколькими истоками и стоками В задаче о максимальном потоке может быль несюлько истоков и стоков. Например, у юмпанни э.пс)гу Рпсй может быть гп фабрик (вы лз,..., л ) н и складов (гэ,1з,..., г„), как показано на рис.
26.3,(а), на ютором приведен пример транспортной сети с пятью истоками и тремя стоками. К счасп ю, эта задача не сложнее, чем обычная задача о максимальном потоке. (эзэ' ~ о' . г:.;.~ /7 ъ,::.' з 'л~' ,х .й га) Рис. 26З. Преобразование задачи о максимальном потоке с несколькими истоками и стоками а задачу с синим истоком н одним стоком. (а) Транспортная сеть с шпъю истоками Я = (ям зз, зз, зю зл) и тремя стоками Т = (гэ, гю гз). (б) Эквивалентная сеть с опиям истоком и синим стоком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
