Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 151
Текст из файла (страница 151)
Некоторые исследователи расширили эти результаты и разработали алгоритмы, предназначенные для поиска кратчайших путей между всеми парами вершин в неориентированных графах с целочисленными весами ребер в диапазоне [1,2,..., И'). Среди таких алгоритмов быстрее всего в асимптотическом пределе ведет себя алгоритм Шошана (Броз)зап) и Цвика (Яичек) [278], время работы которого равно 0 (И" Ъ' р (1' И')). Каргер (Кагйег), Коллер (Ко!1ег) и Филлипс (РЫ!11рз) [170], а также независимо Мак-Геч (МсОеосЬ) [215] дали временную границу, зависящую от Е",— подмножества ребер из множества Е, входящих в некоторый кратчайший путь.
Для заданного графа с неотрицательными весами ребер эти алгоритмы завершают свою работу за время О (1' Е*+ Уз 18 Ъ). Это лучший показатель, чем ~1",- кратное выполнение алгоритма Дейкстры, если ~Е*~ = о (Е). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (1Л)тап) [5] дали определение алгебраичесюй структуры, известной как "замкнутое полуюльцо". Эта структура служит общим каркасом для решения задач о поиске путей в ориентированных графах.
Алгоритм Флойда-Варшалла и описанный в разделе 25.2 алгоритм транзитивного замыкания — примеры алгоритмов поиска путей между всеми парами вершин, основанных на замкнутых полукольцах. Маггс (Маййв) и Плоткин (Р1обс(п) [208] показали, как искать минимальные остовные деревья с помощью замкнутых полуколец. ГЛАВА 26 Задача о максимальном потоке Так же, как дорожную карту можно смоделировать ориентированным графом, чтобы найти кратчайший путь из одной точки в другую, ориентированный граф можно интерпретировать как некоторую транспортную сеть и использовать его для решения задач о потоках вещества в системе трубопроводов. Представим, что некоторый продукт передается по системе от источника, где данный продукт производится, к стоку, где он потребляется.
Источник производит продукт с некоторой постоянной скоростью, а сток с той же скоростью потребляет продукт. Интуитивно потоком продукта в любой точке системы является скорость движения продукта. С помощью транспортных сетей можно моделировать течение жидкостей по трубопроводам, движение деталей на сборочных линиях, передачу тока по электрическим сетям, информации — по информационным сетям и т.д. Каждое ориентированное ребро сети можно рассматривать как канал, по которому движется продукт. Каждый канал имеет заданную пропускную способность, которая характеризует максимальную скорость перемещения продукта по каналу, например, 200 литров жидкости в минуту для трубопровода или 20 ампер для провода электрической цепи. Вершины являются точками пересечения каналов; через вершины, отличные от источника и стока, продукт проходит, не накапливаясь. Иными словами, скорость поступления продукта в вершину должна быть равна скорости его удаления из вершины.
Это свойство называется свойством сохранения потока; в случае передачи тока по электрическим цепям ему соответствует закон Кирхгофа. В задаче о максимальном потоке мы хотим найти максимальную скорость пересылки продукта от источника к стоку, при которой не будут нарушаться ограничения пропускной способности.
Это одна из простейших задач, возникающих Глава 26. Задача о максимальном потоке 735 в транспортных сетях, и, как будет показано в данной главе, существуют эффективные алгоритмы ее решения. Более того, основные методы, используемые в алгоритмах решения задач о максимальном потоке, можно применять для решения других задач, связанных с транспортными сетями. В данной главе предлагается два общих метода решения задачи о максимальном потоке.
В разделе 26.1 формализуются понятия транспортных сетей и потоков, а также дается формальное определение задачи о максимальном потоке. В разделе 26.2 описывается классический метод Форда-Фалкерсона (Рогд апд Ри1кегзол) для поиска максимального потока. В качестве приложения данного метода в разделе 26.3 осуществляется поиск максимального паросочетания в неориентированном двудольном графе. В разделе 26.4 описывается метод "проталкивания предпотока" ("рцзЬ-ге!аЬе1"), который лежит в основе многих наиболее быстрых алгоритмов для задач в транспортных сетях. В разделе 26.5 рассматривается еще один алгоритм, время работы которого составляет О (1'з). Хотя он и не является самым быстрым известным алгоритмом, зато позволяет проиллюстрировать некоторые методы, используемые в асимптотически более быстрых алгоритмах, и на практике является достаточно эффективным.
26.1 Транспортные сети В данном разделе мы дадим определение транспортных сетей в терминах теории графов, обсудим их свойства, дадим точное определение задачи о максимальном потоке, а также введем некие полезные обозначения. Транспортные сети и потоки Транспортная сеть (бои пепчогк) С = (КЕ) представляет собой ориентированный граф, в котором каждое ребро (и, и) е Е имеет неотрицательную пропускнуго способность (сарасйу) с(и,и) > О. Если (и,и) ф Е, предполагается, что с (и, и) = О.
В транспортной сети выделяются две вершины: источник (зощсе) а и сток (гйп1с) 1. Для удобства предполагается, что каждая вершина лежит на неком пути из источника к стоку, т.е. для любой вершины и е У существует путь в - и - 1. Таким образом, граф является связным и 1Е! > 1Ц вЂ” 1. На рис. 26.1а показан пример транспортной сети С = (К Е) для задачи грузовых перевозок компании 1лску РисЕ Источник в — это фабрика в Ванкувере, а сток г — склад в Виннипеге. Шайбы доставляются через промежуточные города, но за день из города и в город и можно отправить только с(и, и) ящиков. На рисунке приведена пропускная способность каждого ребра сети.
На рис. 26.16 показаны потоки в транспортной сети. Поток У в сети С имеет значение 1г"1 = 19. Показаны только положительные потоки. Если г" (и, и) > О, то ребро (и, и) снабжено меткой )'(и, и)/с (и, и) (косая черта используется только для того, чтобы отделить Часть Ч1. Алгоритмы для работы с графами 736 цвотзч С~скатю /г -,У ~ ~яу~ Хыгат Рнчт а) б) Рис.
26Д. Пример транспортной сети и ее потоки поток от пропускной способности и не обозначает деление). Если Г' (и, и) < О, то у ребра (и, и) показана толью его пропускная способность. Теперь дадим формальное определение потоков. Пусть С = (Ч; Е) — транспортная сеть с функцией пропускной способности с. Пусть з — источник, а г— сток. Потоком (йот) в С является действительная функция Г: У х У -+ В„ удовлетворяющая следующим трем условиям. Ограничение пропускной способности (сарасйу сопзпашг): у (и,и) < с(и,з) для всех и, и Е У.
Антисимметрнчночть (з1сет зупипену): Г' (и, о) = — Г' (и, и) для всех и, и Е У. Сохранение потока (йот сопзегчайоп): для всех и Е У вЂ” (з, г) ~~) г(и,и) =О. Количество г'(и, и), которое может быть положительным, нулевым или отрицательным, называется потокам (йо)ч) из вершины и в вершину и. Величина (ча)ве) потока ~ определяется как И=~ ~У( и) (26.1) чаи т.е. как суммарный поток, выходящий из источника (в данном случае Н обозначает величину потока, а не абсолютную величину или мощность). В задаче о максамальном потоке (шахппшп йот ргоЫеш) дана некоторая транспортная сеть С с источником з и стоюм 1, и необходимо найти поток максимальной величины. Перед тем как рассматривать пример задачи о потоке в сети, кратко проанализируем три свойства потока.
Ограничение пропускной способности предполагает, чтобы поток из одной вершины в другую не превышал заданную пропускную способность ребра. Антисимметричность введена для удобства обозначений и заключается в том, что поток из вершины и в вершину и противоположен потоку в обратном направлении. Свойство сохранения потока утверждает, что суммарный поток, выходящий из вершины, не являющейся источниюм или стоком, равен Глава 26. Задача о максимальном потоке 737 нулю.
Используя антисимметричность, можно записать свойство сохранения по- тока как У(и,и) = О для всех и й У вЂ” (а, 1), т.е. суммарный поток, входящий в вершину, отличную от источника и стока, равен О. Если в Е не присутствуют ни (и, и), ни (и, и), между вершинами и и и нет потока, и у (и, и) = Г" (и, и) = О. (В упражнении 26.1-! предлагается формально доказать это свойство.) Последнее наблюдение касается свойств, связанных с положительными потоками.
Суммарный положительный поток (соса! роз!сне йож), входящий в вершину и, задается выражением г (и, и). (26.2) Суммарный положительный поток, выходящий из некоторой вершины, определяется симметрично. Суммарным чистый поток (соса! пес йоч) в некоторой вершине равен разности суммарного положительного потока, выходящего из данной вершины, и суммарного положительного потока, входящего в нее. Одна из интерпретаций свойства сохранения потока состоит в том, что для отличной от источника и стока вершины входящий в нее суммарный положительный поток должен быть равен выходящему суммарному положительному потоку.
Свойство, что суммарный чистый поток в транзитной вершине должен быть равен О, часто нестрого формулируют как "входящий поток равен выходящему потоку". Пример потока С помощью транспортной сети можно моделировать задачу о грузовых перевозках, представленную на рис. 26.1а. У компании 1лс1су Рис1с в Ванкувере есть фабрика (источник а), производящая хоккейные шайбы, а в Виннипеге — склад (сток с), где эти шайбы хранятся. Компания арендует места на грузовиках других фирм для доставки шайб с фабрики на склад. Поскольку грузовики ездят по определенным маршрутам (ребрам) между городами (вершинами) и имеют ограниченную грузоподъемность, компания Ьис1су РисЕ может перевозить не более с(и, и) ящиков в день между каждой парой городов и и и, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
