Задача о максимальном потоке. Алгоритм Форда. Теорема Форда-Фалкерсона

МИНЕСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЯ ОБРАЗОВАНИЯ "БРЕСТСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ А.С. ПУШКИНА"

ЮРИДИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра математического моделирования

КУРСОВАЯ РАБОТА

на тему: Задача о максимальном потоке. Алгоритм Форда. Теорема Форда-Фалкерсона.

              Выполнил

              студент 4 курса

              специальности Бизнес-администрирование

              группы                                                                         Антонюк Ю.В.

                                                 подпись                            Ф.И.О

Руководитель                                          Якубович А.П.

                                                 подпись                             Ф.И.О

Брест 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ              3

1 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ              4

1.1 Постановка потоковых задач              4

1.2 История развития алгоритмов решение задачи о максимальном потоке              7             

2 ТЕОРЕМА ФОРДА - ФАЛКЕРСОНА              12

3 АЛГОРИТМ ФОРДА - ФАЛКЕРСОНА              17

ЗАКЛЮЧЕНИЕ              21

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ              22

ВВЕДЕНИЕ

Задачи теории потоков в сетях являются одними из основных в исследовании операций, computer science и инженерном деле. Теория потоков имеет многочисленные приложения в реально возникающих задачах.

Теория потоков в сетях развилась и развивается сегодня в лучших традициях прикладной математики: она родилась среди разнообразных прикладных проблем и продолжает вносить практический вклад в решение многих прикладных задач. Эта теория установила под собой сильную методологическую основу и сформулировала многочисленные стимулирующие вычислительные проблемы. Кроме того, исследования в области теории потоков сильно связаны с исследованиями в дискретной математике и оптимизации, которые не имеют определенной связи с сетями. Например, разработка методов разложения целых чисел, теория матройдов, и множества задач связанных с двойственностью.

К теории потоков относятся различные задачи, которые можно классифицировать следующим образом. Задачи транспортного типа – транспортная задача, поиск пути минимальной длины, поиск циклов отрицательного веса (неоптимальных перевозок) и т. д. Задачи определения существования потока – задача о максимальном потоке и, двойственная к ней, задача поиска минимального разреза. А также задача о поиске обобщенного потока – потока с потерями и приобретениями.

В этой работе рассматриваются элементы исторического развития задач, связанных с поиском максимального потока: историю появление новых методов, структур данных, приемов, связанных с необходимостью находить все более эффективные или все более обобщенные алгоритмы для решения все больше возникающих прикладных задач, так или иначе приводимых к задаче поиска максимального потока в сети.

1 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

1.1 Постановки потоковых задач

Здесь приводится классические и наиболее часто используемые варианты постановки задач теории потоков. Начнем с общей задачи теории потоков.

Пусть G=(V,E) – ориентированный граф, в котором V – множество вершин и E – множество дуг. На множестве дуг графа заданы две функции: c(i,j) – цена дуги (i,j) и u(i,j) – пропускная способность дуги (i,j). Предположим, что паре вершин однозначно соответствует дуга, если она есть. Для каждой вершины iV определим величину bi – потребность в обеспечении. Эта величина показывает, сколько вещества требуется данному стратегическому пункту или сколько вещества в этом пункте в избытке. Если bi0, то пункт i называется пунктом производства (вещество в избытке), если bi0, то пункт i называется пунктом потребления (вещество в недостатке). Если же bi=0, то речь идет о транзитном пункте. С этими обозначениями общая задача теории потоков (она же задача поиска потока минимальной стоимости в общем виде, она же – транспортная задача) запишется следующим образом:

Вектор x=(xij) называется потоком в сети G. Первое ограничение задачи (уравнения баланса) показывает, что поток, проходящий через вершину, должен оставлять (или забирать) ровно необходимое ей количество вещества. Последнее ограничение запрещает превышение пропускной способности дуг сети. Речь идет о поиске оптимального (в смысле транспортных затрат) способа доставки товара (вещества) из пунктов потребления в пункты производства. Задача не имеет решения, если не выполнено условие баланса

однако замкнуть (сбалансировать) задачу можно путем добавления фиктивной вершины, которая будет иметь потенциал, равный

Особую роль в теории потоков и в истории ее развития имеют следующие частные случаи модели.

Пусть имеются две особые вершины s,tV. Пусть Cjj означает длину дороги из пункта i в пункт j. Требуется найти кратчайший путь из s в t. Для решения задачи о поиске кратчайшего пути, положим в общей модели bs=1 и bt=-1, а для остальных вершин iV/s.t положим bi=0. Выберем uij=1 для всех дуг сети. Решением задачи поиска потока в этом случае будет является кратчайший путь из пункта s в пункт t.

Пусть мы имеем, как и в предыдущем случае две особых вершины: s, которую будем называть истоком, и t, называемую стоком. И мы хотим определить максимальное количество вещества, которое можно перемещать из истока в сток, не превышая пропускных способностей дуг сети и с тем условием, что при перемещении вещество не может накапливаться в вершинах. Для решения этой задачи положим bi=0 для всех, iV,cij=0 для всех (i,j)E и введем дополнительную дугу (t,s), для которой положим cis=-1 и uis=. Такая задача называется задачей поиска максимального потока в сети. Речь идет о том, чтобы найти способ перемещать в единицу времени как можно больше вещества из истока в сток (то же самое, что максимизировать поток, идущий обратно по дуге из t в s).

В 1956 году классическая задача поиска максимального потока была поставлена Фордом и Фалкерсоном и записана уже не в терминах задачи линейного программирования, а в терминах новой теории – теории потоков. Ими же отдельно сформулирована задача поиска максимального потока и предложен первый алгоритм ее решения, не имеющий ничего общего с симплексным методом, которым подобная задача, поставленная в терминах задачи линейного программирования решалась Данцигом.

Кроме задачи поиска максимального потока, рассматривается задача поиска потока минимальной стоимости так же имеющая свои особенности, которые выходят за пределы нашей работы.

Эти задачи – о кратчайшем пути, о максимальном потоке, о потоке минимальной стоимости (транспортная задача) – получили широкое применение в различных областях человеческой деятельности и каждая из них развивалась своим путем. Было разработано множество алгоритмов, которые находят решения потоковых задач в их частных случаях, и каждый новый алгоритм нес в себе идею, которая могла быть применена к каждой вариации общей задачи теории потоков в том или ином виде. Было разработано множество структур данных, которые обобщались и на многие другие задачи и прикладной математики.

1.2 История развития алгоритмов решение задачи о максимальном потоке

История развития алгоритмов решения задачи о максимальном потоке

Задача поиска максимального потока в сети в общем случае решается так же, как и известная на тот момент транспортная задача. Симплексный метод специально для этой задачи был модифицирован в 1951 году Данцигом. Алгоритм не был полиномиальным, как и любой симплексный метод. Однако специальный вид задачи позволил предположить, что для ее решения можно применить более простые и быстрые алгоритмы. Первый такой алгоритм, который не похож на симплексный метод, был разработан Фордом и Фалкерсоном в 1956 году. Время работы этого алгоритма не было полиномиальным (таблица 1), однако его идея и его математическое обоснование как раз и легли в основу качественной теории потоков. В предложенном методе использовалась идея «дополняющих путей».

В 1970 году Эдмондс, Карп и, независимо от них Диниц, улучшили алгоритм Форда и Фалкерсона, доказав теорему о том, что алгоритм выполняется за полиномиальное время, если на каждом его шаге использовать увеличивающие цепочки минимальной длины.

В следующем десятилетии алгоритмы поиска максимального потока стали быстрее благодаря новым мощным технологиям. Одну из таких технологий ввел Диниц – его идея блокирующий потоков, основанная на идее кратчайших путей, позволила не только достигнуть новых временных границ, но и дала богатую почву для новых изобретений. Однако Диниц не занимался отдельно задачей поиска блокирующего потока, показав лишь, что даже самый простой метод (1970 год) значительно улучшает оценку Эдмондса и Капа. Карзанов, разрабатывая новые методы поиска блокирующих потоков, развил идею «предпотоков», которая позволила получить самый быстрый на тот момент алгоритм поиска максимального потока для плотных сетей с оценкой O(n3). Алгоритм получил название «волновой» – название, символизирующее идею движения волны (1974 год). Еще одно изобретение в области алгоритмов – масштабирование – было создано Эдмондсом, Карпом и, независимо от них, Диницем (1972 год). Идея масштабирования пропускных способностей сети, однако, требовала, чтобы сами пропускные способности были целыми числами. Оценка времени работы алгоритмов масштабирования была псевдополиномиальной.

Идея масштабирования заключается в декомпозиции задачи поиска максимального потока не подзадачи, называемые ∆-фазами. В процессе        ∆-фазы увеличение потока происходит только вдоль путей с пропускной способностью не меньшей ∆. Когда все такие пути исчерпаны, осуществляется переход на новую фазу масштабирования, путем деления ∆ на два (нацело). На последней фазе ∆=1 – выбираются любые пути, откуда следует, что в конце работы будет найден максимальный поток с точностью до 1 – это максимальная точность для сети с целыми пропускными способностями. Так как каждый раз ∆ делится на 2 нацело, требуется не более чем log2U ∆ -фаз. В 1973 году Диниц и независимо от него Габов разработали новую, другую, схему выполнения каждой отдельной фазы, не такую, которую ипользовали Эдмондс и Карп. Это позволило впервые получить оценку времени работы, в которой множитель O(nm) входит в первой степени, если опустить влияние, как правило, небольшой величины O(logU).

Таблица 1 История улучшений сложности алгоритмов поиска

максимального потока.

История улучшений сложности алгоритмов поиска максимального потока. Оценки, содержащие U (зависят от максимальной пропускной способности), - применяются к сетям с целыми пропускными способностями. n - число вершин в сети, m - число ребер.

В 1970 году Диниц разработал идею блокирующих потоков, которая, как уже было сказано, привнесла множество открытий в области разработки алгоритмов поиска максимального потока. Многие алгоритмы отличаются только способом поиска блокирующих потоков, которых было придумано огромное множество. Например, Йоши Шилочь использовал сбалансированные деревья, чтобы научиться находить блокирующий поток за время O(I log2I), где I=n+m.

В 1974 году идея предпотоков Карзанова также продвинула алгоритмы к новой оценке – O(n3) , которая до конца XX века являлась лучшей для произвольных плотных сетей. И не только это было открытием – идея предпотоков была использована Голдбергом для создания совершенно новой идеи поиска потоков – методов проталкивания самый простой из которых выполнялся за время O(n2m), а его несложные модификации 4 позволили получить оценку O(n3, чем Голдберг и повторил результат Карзанова. На сегодняшний день самые быстрые алгоритмы используют именно идею проталкивания. В 1986 году Голдберг и Тарьян разработали новый алгоритм на основе проталкивания, позволивший достигнуть оценки O(nm log(n2/m))Алгоритм использует структуру данный, называемую деревом Слейтора-Тарьяна. В 1983 году Слейтор и Тарьян использовали эту структуру для усовершенствования алгорима Диница, чем получили оценку O(nm log n).

В 1987 году Ахъюджи и Орлин объединили идеи Голдберга и идею масштабирования, получив оценку O(nm+n2log U). В отличие от Габова и Диница, они масштабировали не пропускную способность ребер, а избыток потока в вершине в алгоритме «проталкивания предпотока» Голдберга. Несложная модификация их метода (без использования таких структур, как сбалансированные или динамические деревья) выполнялась за время O(nmlog(n/m*√ log U)) .

Для единичный сетей Карзанов и независимо от него Тарьян и Эвен показали, что алгоритм Диница, использующий блокирующие потоки требует всего лишь O(min(n2/3, m1/2)m) для графов без мультидуг и O(m3/2) для мультиграфов. Этот эффект достигается как раз за счет идеи приближения максимального потока последовательностью блокирующих потоков, которая для единичных сетей сходится быстрее. Было обнаружено, что поиск максимального потока для таких сетей может быть отдельной задачей, которая обладает своими особенными свойствами. Кроме единичных сетей так же рассматривались простые сети – для них алгоритм Диница выполняется за время O(m√n), что позволило достигнуть новой оценки для задачи о максимальном паросочетании.

Задачи поиска максимального потока поделились на два основных класса – поиск максимального потока в сети с целыми пропускными способностями в сети с единичными пропускными способностями. Долгое время алгоритмы поиска максимального потока в сети с целыми пропускными способностями «держались» на оценке, близкой к O(nm), однако были «хуже» нее, в то время как алгоритмы для единичных сетей эту оценку сильно превзошли. Но в 1997 году Голдберг и Рао использовали идею нелинейной функции расстояния, идеи Диница и деревья Слейтора-Тарьяна, чтобы получить алгоритм с оценкой

который и на сегодняшний день остается самым быстрым и который резко сократил расстояние между единичными и целочисленными сетями, показав, что оценка O(nm) даже очень скромная для задачи поиска максимального потока.

Идея нелинейной функции расстояния была придумана еще Эдмондсом и Карпом, однако она не давала такого существенного улучшения оценки. Эдмондс и Карп использовали нелинейную функцию расстояния в градиентной модификации метода Форда-Фалкерсона. На каждом шаге выполнялся поиск самого пропускного пути, для чего требовалось модифицировать алгоритм Дейкстры для поиска пути минимальной длины. Новый алгоритм давал незначительное улучшение оценки и не получил широкого распространения, однако идея использования нелинейной функции расстояния, как мы видим была реабилитирована Голбергом и Рао.

В процессе работы над совершенствованием алгоритмов было изобретено несколько структур данных. Например, как уже упоминалось, в 1978 году Шилочь использовал сбалансированные деревья для своей структуры данных, поддерживающей быструю работу с дополняющими путями, что позволило усовершенствовать алгоритм поиска блокирующего потока и получить новую оценку. Слейтор и Тарьян разработали специальную структуру динамических деревьев, с помощью которой в 1983 году пыла получена новая для того времени оценка сложности поиска блокирующего потока – O(m log n). Деревья Слейтора-Тарьяна получили широкое применение для решения многих других задач, таких, как задача о поиске наименьшего общего предка, поиске минимального покрывающего дерева и т. д. Кроме этого, современные быстрые алгоритмы используют именно эту структуру данных.

2 ТЕОРЕМА ФОРДА - ФАЛКЕРСОНА

Сетью называется связный граф (обычно, не орграф и не мультиграф), в котором заданы “пропускные способности” ребер, т. е. числа qij. Это числа большие или равные нулю, причем qij = 0 тогда и только тогда, когда нет ребра, соединяющего вершины i и j. Таким образом, можно считать, что пропускные способности ребер заданы для любой пары вершин. В дискретной математике пропускные способности ребер, как и все возникающие константы, считаются целыми числами (или рациональными, что одно и то же, так как рациональные числа отличаются от целых только единицами измерения). Заметим, что сети имеют огромные приложения, в частности, “сети планирования” (имеется в виду планирование производства некоторых новых, достаточно сложных изделий), где “пропускные способности” ребер – это время, за которое нужно из нескольких узлов изделия (вершин графа) получить другой (более сложный) узел. Сетевое планирование здесь не исследуется, так как гораздо больший интерес представляет сеть связи, где пропускные способности ребер – это обычно “количество одновременных разговоров”, которые могут происходить между телефонными узлами (вершинами графа).

Потоком в сети между вершиной t (источником) и s (стоком) называется набор чисел cij, (т. е. количество условного “груза”, перевозимого из вершины с номером i в вершину с номером j), удовлетворяющих четырем условиям:

1) числа cij Ј  0, причем если cij > 0, то cji = 0 (нет встречных перевозок);

2) числа cij Ј  qij (соответствующих пропускных способностей ребер);

3) если вершина с номером i – промежуточная (не совпадает с источником и стоком), то

т. е. количество “груза”, вывозимого из вершины i, равно количеству “груза”, ввозимого в эту вершину;

4) количество “груза”, вывозимого из источника t, должно быть равно количеству груза, ввозимого в сток s:

Число А называется величиной данного потока или просто потоком между t и s.

Для дальнейшего нужно следующее определение:

Пусть имеется некоторое сечение между вершинами t и s. Тогда величиной сечения называется сумма пропускных способностей ребер, входящих в это сечение. Сечение называется минимальным (максимальным), если его величина минимальна (максимальна).

Теорема Форда – Фалкерсона (1955). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами.

Доказательство этой теоремы является конструктивным (т. е. показывает, как найти нужный максимальный поток), поэтому приводится ниже.

Докажем сначала, что любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин “грузов”, перевозимых по всем возможным путям из вершины t в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести “груза” больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна, сумме всех пропускных способностей ребер данного сечения. Утверждение доказано.

Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения.

1. Докажем теперь обратное неравенство. Пусть имеется некоторый поток cij (какой-то поток всегда существует, например, нулевой, когда все cij = 0). Будем помечать вершины графа, причем считаем, что все помеченные вершины образуют множество Y. Пометки вершин производятся от источника. Каждая пометка вершины (если эта вершина может быть помечена) состоит из двух чисел: первое – это “+” или “–” номер вершины (из Y), c которой связана новая помечаемая вершина, и второе – (обязательно должно быть положительным) – это фактически та добавка к потоку, которая может быть дополнительно “довезена” в эту вершину из источника по сравнению с исходным потоком.

Более точно, множество помеченных вершин Y образуется следующим образом:

источник t принадлежит Y и его пометка (0,Ґ ); второе число, условно говоря, равно бесконечности – что для дискретной математики означает, что это настолько большое число, как нам понадобится;

если вершина i принадлежит Y и cij < qij (дуга (i,j) – прямая и ненасыщенная), то вершина j также принадлежит Y и пометка вершины j равна (+i, dj), где dj >0 равно dj = min { dj, qij – cij }. Заметим, что здесь число di – это второе число уже помеченной вершины i, а знак + перед номером i означает, что дуга, связывающая вершины (i, j) является прямой (и ненасыщенной);

если вершина к принадлежит Y и cik > 0 (обратная дуга), то вершина с номером j также должна принадлежать Y и ее пометка равна (– к, dj), где знак минус означает, что вершина j связана с уже помеченной вершиной к обратной дугой, dj = min{ dk, qik + cik }, причем очевидно, что dj также строго больше нуля. Таким образом, построение множества Y является индуктивным, т. е. новая вершина добавляется в Y, если она связана с некоторой вершиной уже входящей в Y либо прямой ненасыщенной дугой, либо обратной дугой.

После того как построение множества Y закончено (к нему нельзя добавить новых вершин), возможны 2 случая.

1. Сток (т. е. вершина с номером s) не входит в множество вершин Y. Тогда обозначим множество вершин, не входящих в Y через Z. Наш граф по условию является связным, поэтому из Y, в Z идут некоторые ребра. По правилам построения Y все эти ребра являются прямыми насыщенными дугами (рис. 1).

Ребра, идущие из множества Y в Z, образуют сечение между вершинами t и s. Видно также, что сумма пропускных способностей ребер этого сечения (а все эти ребра являются прямыми, насыщенными) равна потоку из t в s. Значит, данный поток является максимальным (так как он равен величине некоторого сечения), а данное сечение является минимальным.

Рис.1

2. Вершина s также входит в Y, и пусть второе число ее пометки d s > 0. Тогда, очевидно, что между вершинами t и s существует цепь (состоящая из направленных ребер – прямых и обратных дуг), соединяющая эти вершины

Схематично это представлено на рис. 2

      t ® ·®·¬ ·¬·® ·®·¬ ·¬·®·®s

Заметим, что дуга, выходящая из источника, и дуга, входящая в сток, должны быть обязательно прямыми. Прибавим ds к cij для прямых дуг этой цепи (по построению видно, что полученное число будет меньше или равно qij) и вычтем это d s из cij для обратных дуг (может получиться отрицательное число, но оно обязательно будет по абсолютной величине меньше qij, так как по построению ds Ј cij + qij , а это означает, что обратная дуга меняет направление, становится прямой дугой и его “нагрузка” будет равна модулю числа

Тогда новые числа для дуг, входящих в нашу цепь, а также “старые” cij для всех дуг, не входящих в нашу цепь, образуют новый поток из вершины t в вершину s (легко проверить простым рассуждением, что для новых чисел выполняются условия (1)–(4)). Кроме того, величина нового потока по сравнению со старым увеличилась на ds > 0  . Для нового потока снова проведем ту же процедуру и т. д.

Так как каждый раз величина потока увеличивается, по крайней мере, на 1 (пропускные способности ребер являются целыми числами), а величина максимального потока ограничена (величиной минимального сечения), то эта процедура не может продолжаться бесконечно и, значит, на каком-то шаге получим поток, для которого вершина s не входит в Y, т. е. поток является максимальным и величина его равна величине минимального сечения. Теорема доказана.

Рассуждение теоремы Форда – Фалкерсона фактически является алгоритмом нахождения максимального потока между двумя вершинами (или доказательством того, что этот поток является максимальным). Примечание. Если в данном графе с пропускными способностями ребер (т. е. сети) имеется несколько источников и несколько стоков, то описанный выше алгоритм можно применить следующим образом. Вводим новый источник и новый сток, причем новый источник соединяем ребрами со всеми источниками, а новый сток – со всеми стоками, при этом пропускные способности новых ребер считаем сколь угодно большими числами, так что эти дуги в любом возможном потоке были бы ненасыщенными (напомним, что ребра, идущие из источника и ребра, идущие в сток всегда являются прямыми дугами). После этого для нового графа решаем задачу о максимальном потоке (из одного нового источника в один новый сток). Решив ее, стираем все введенные ребра и вершины.

3. АЛГОРИТМ ФОРДА - ФАЛКЕРСОНА

Рассмотрим алгоритм Форда-Фалкерсона для фиксированной конфигурации сети.

Идея алгоритма

Алгоритм начинает работу с начального допустимого потока (возможно, нулевого). Затем осуществляются попытки увеличить величину потока с помощью систематического поиска всех возможных цепей из s в t, на которых можно увеличить величину потока (дополняющие цепи).

Поиск дополняющих цепей производится путем расстановки меток, которые указывают, на каких дугах и на сколько можно увеличить поток. Когда найдена одна из таких цепей, поток вдоль нее увеличивается. После чего все метки стираются, и вновь полученный поток используется в качестве исходного при новой расстановке меток.

Алгоритм заканчивает работу, когда нельзя найти ни одну дополняющую цепь. Последний найденный поток является максимальным.