Реализация метод форда фалкерсона

Добавил пользователь Алексей Ф.
Обновлено: 19.09.2024

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

  • Open with Desktop
  • View raw
  • Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Максимальный поток в сети

Как и большинство других алгоритмов нахождения максимального потока, алгоритм Форда-Фалкерсона работает на остаточной сети, построенной на основе исходного графа. Сам алгоритм заключается в нахождении раз за разом (увеличивающего) пути от источника к стоку и проталкивании максимального потока по этому пути с ограничением на пропускную способность ребер. Как только путь от источника к стоку перестает существовать, алгоритм завершается.

Запишем все вышесказанное в виде кода, где неуточненные места вынесены в функции, с которыми мы будем разбираться позднее. Итак, наше решение заключено в функцию max_flow , которая принимает две вершины s (источник) и t (сток). Очевидно, что если источник и сток совпадают, то алгоритм можно не запускать. Сам алгоритм работает на уже построенной остаточной сети и описан в функции ford_fulkerson . В ней мы в цикле пытаемся построить какой-нибудь путь от вершины s . Если при этом вершина t даже не была посещена, то пути не существует, и алгоритм завершится. Если же вершина t была посещена, то путь от s к t существует, и мы его восстанавливаем. Затем мы находим максимальную величину потока, который еще можно протолкнуть по найденному пути, и увеличиваем поток на эту величину по всем ребрам пути.

При эффективной реализации на списках смежности и с целочисленными пропускными способностями алгоритм может достигать времени работы O((n + m)f) , где f -- величина максимального потока. Каждый найденный путь увеличивает поток хотя бы на 1 , а поиск пути может быть выполнен за O(m) . Обнуление массивов pred и visited выполняется за O(n) на каждой итерации.

Некоторые части алгоритма мы вынесли в отдельные функции. Теперь пора их реализовать.

Начнем с поиска пути. Воспользуемся для этого поиском в глубину, при этом будем запоминать ребро, по которому мы пришли в вершину, в массиве pred и помечать посещенные вершины в массиве visited . Одним отличием от обычного поиска в глубину является то, что мы не можем перейти по ребру, если оно заблокировано потоком (по ребру пущен поток величиной равной пропускной способности ребра).

Так как мы работаем не с исходным графом, а с остаточной сетью, то введем дополнительные функции для работы с ней: edges (получение исходящих ребер в остаточной сети), target (получение конечной вершины дуги), available (вычисление доступной пропускной способности).

Следующим этапом является восстановление пути по массиву pred . Начиная со стока t , будем по ребрам перемещаться все ближе к источнику s . В этой цепочке вершин s -- единственная вершина, у которой нет ребра, по которому в нее пришли, так как с нее был начат обход. Именно по этому критерию мы завершим восстановление пути.

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

Максимальная величина потока, который можно протолкнуть по найденному пути, равна наименьшей остаточной пропускной способности среди ребер этого пути, поэтому пройдем по всем ребрам пути и найдем минимум. Воспользуемся фактом, что путь содержит хотя бы одно ребро (следует из условия, что s != t ), взяв за базовое значение остаточную пропускную способность первого ребра в пути.

Эта функция может быть также упрощена до одной строчки:

Проталкивание потока вдоль пути заключается увеличении потока вдоль каждого из ребер пути на указанную величину. Для этого введем функцию push , которая увеличивает поток вдоль одного ребра.

Возможная реализация остаточной сети

Остались не описаны следующие функции:

  • build_network для построения остаточной сети на основе исходного графа
  • source для получения начальной вершины ребра в остаточной сети
  • target для получения конечной вершины ребра в остаточной сети
  • available для получения остаточной пропускной способности ребра
  • flow для получения величины потока, пропущенного по ребру
  • edges для получения исходящих из вершины ребер в остаточной сети
  • push для увеличения потока вдоль ребра в остаточной сети

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

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

Каждому ребру (v, cu, u) в графе ставится в соответствие два ребра в остаточной сети: (v, cu, u) и (u, 0, v) . При этом изначально по ним пропущен поток величины 0 . Будем хранить ребра остаточной сети в виде списка, причем каждая пара ребер будет занимать позиции 2i и 2i + 1 . Таким образом, по четности индекса легко определить индекс обратного ребра. Более того, эту операцию легко выразить через ^ 1 ( xor 1 ), так как (2i) ^ 1 = 2i + 1 и, соответственно, (2i + 1) ^ 1 = 2i .

Саму остаточную сеть будем, как и исходный граф, представлять в виде списков смежности, но с одним отличием: вместо пары (пропускная способность, вершина) будем хранить индекс ребра в списке ребер.

Таким образом, достаточно легко реализовать работающие за константу недостающие функции.

При увеличении потока по ребру в остаточной сети необходимо уменьшить поток в обратном ребре на ту же величину.

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

Сам каркас алгоритма при этом останется неизменным.

Каждая итерация алгоритма выполняется за O(n + m) . Каждый следующий найденный данным алгоритмом увеличивающий путь будет не короче предыдущего. При нахождении увеличивающего пути хотя бы одно ребро блокируется потоком и может стать вновь доступно лишь при проталкивании потока по обратному ребру, что может случиться лишь при более длинном увеличивающем пути. Так как увеличивающий путь кратчайший, его длина не превосходит n - 1 . Таким образом, число итераций составляет O(nm) . Получаем время работы алгоритма O((n+m)nm) .

Максимальный поток минимальной стоимости

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

Добавим удельную стоимость к представлению ребра, а также определим новую функцию cost к нашей абстракции, которая возвращает удельную стоимость для переданного ребра:

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

Существует несколько алгоритмов нахождения максимального потока минимальной стоимости. Мы рассмотрим два из них.

Строим сразу поток минимальной стоимости

Первый подход заключается в изначальном построении потока минимальной стоимости, с постепенным увеличением его величины, пока не получим максимальный поток. При этом на каждой итерации мы получаем поток минимальной стоимости для данной величины. Этот алгоритм называется алгоритмом Басакера-Гоуэна, и его тоже можно рассматривать как некоторую модификацию алгоритма Форда-Фалкерсона. Отличие опять же заключается в поиске увеличивающего пути. Алгоритм предлагает искать кратчайшие по удельной стоимости пути в остаточной сети.

Приведем сначала каркас алгоритма. Заметим, что теперь мы считаем не только величину потока, но и его стоимость. Также мы ввели новую функцию path_cost , которая вычисляет удельную стоимость потока для найденного пути.

Функция path_cost достаточно проста и очевидна, так что начнем с нее. Удельной стоимостью потока для пути является сумма удельных стоимостей ребер, входящих в этот путь.

Теперь вернемся к функции find_path . Как уже говорилось, мы должны огранизовать поиск кратчайшего по удельной стоимости пути. Так как обратные ребра имеют отрицательную стоимость, то мы можем использовать алгоритм Форда-Беллмана. Так как на каждом этапе мы находим поток наименьшей стоимости, то отрицательных циклов в остаточной сети не имеется, и алгоритм отработает корректно. Также нельзя забывать про то, что ребро в сети должно обрабатываться только при условии, если его остаточная пропускная способность положительна.

Так как Форд-Беллман работает со списком ребер, то добавим функцию его получения к абстракции:

Уменьшаем стоимость потока

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

Сначала представим каркас нашего алгоритма:

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

Теперь перейдем к функции remove_cycles . В ней мы будем в цикле искать отрицательные циклы, пропускать по ним поток, устраняя их и тем самым уменьшая стоимость потока. Как только отрицательный цикл не найден, алгоритм можно завершать. Также нельзя начинать поиск цикла из вершины s , так как в остаточной сети, по которой уже пропущен максимальный поток, некоторые вершины и, соответственно, циклы могут быть недостижимы из вершины s . Поэтому начнем алгоритм "одновременно" из всех вершин сети, присвоив им значение 0 в массиве dist (при этом физический смысл значений в массиве теряется).

Находить цикл отрицательной стоимости будем с помощью алгоритма Форда-Беллмана. Если на последней итерации алгоритма была найдена вершина, для которой проведена релаксация, то эта вершина достижима из искомого цикла, и именно ее мы вернем.

Теперь, когда у нас есть вершина u , достижимая из цикла, мы можем добраться до вершины v , принадлежащей циклу, следуя по массиву pred . Так как на n-й итерации алгоритма Форда-Беллмана мы построили кратчайшие пути длины не более n , то достаточно пройти назад по ребрам n раз, чтобы гарантированно попасть в цикл. Затем, начиная от вершины v , мы можем восстановить все ребра цикла, следуя по массиву pred , пока вновь не встретим вершину v .

Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.

При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

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

Исходный граф

Исходный граф

Как работает сам алгоритм?

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

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

Возвращать определенное количество потока из соседних вершин в текущую.

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

Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.

Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

Возвращаемся обратно к нахождению пути в остаточной сети после модификации.

Разбор конкретного примера

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

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

Сколько потока можем провести по этому пути.
- Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .

Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

На 4-ой итерации находим следующий путь в остаточной сети:

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть

Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.

Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

Алгоритм Форда-Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.

Содержание

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение [math]0[/math] : [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math] . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника [math]s[/math] к стоку [math]t[/math] , вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено [math]O(|E|f)[/math] , где [math]E[/math] — число рёбер в графе, [math]f[/math] — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за [math]O(E)[/math] и увеличивает поток как минимум на [math]1[/math] .


Рассмотрим приведённую справа сеть с источником [math]\ s[/math] , стоком [math]\ t[/math] , пропускными способностями рёбер [math]\ e_1[/math] , [math]\ e_2[/math] и [math]\ e_3[/math] соответственно [math]\ 1[/math] , [math]r=\dfrac-1>[/math] и [math]\ 1[/math] и пропускной способностью всех остальных рёбер, равной целому числу [math]M \geqslant 2[/math] . Константа [math]\ r[/math] выбрана так, что [math]\ r^2 = 1 - r[/math] . Мы используем пути из остаточного графа, приведённые в таблице, причём [math]\ p_1 = \< s, v_4, v_3, v_2, v_1, t \>[/math] , [math]\ p_2 = \< s, v_2, v_3, v_4, t \>[/math] и [math]\ p_3 = \< s, v_1, v_2, v_3, t \>[/math] .

Шаг Найденный путь Добавленный поток Остаточные пропускные способности
[math]e_1[/math] [math]e_2[/math] [math]e_3[/math]
[math]0[/math] [math]-[/math] [math]-[/math] [math]r^0=1[/math] [math]r[/math] [math]1[/math]
[math]1[/math] [math]\< s, v_2, v_3, t \>[/math] [math]1[/math] [math]r^0[/math] [math]r^1[/math] [math]0[/math]
[math]2[/math] [math]p_1[/math] [math]r^1[/math] [math]r^2[/math] [math]0[/math] [math]r^1[/math]
[math]3[/math] [math]p_2[/math] [math]r^1[/math] [math]r^2[/math] [math]r^1[/math] [math]0[/math]
[math]4[/math] [math]p_1[/math] [math]r^2[/math] [math]0[/math] [math]r^3[/math] [math]r^2[/math]
[math]5[/math] [math]p_3[/math] [math]r^2[/math] [math]r^2[/math] [math]r^3[/math] [math]0[/math]

Заметим, что после шага [math]1[/math] , как и после шага [math]5[/math] , остаточные способности рёбер [math]e_1[/math] , [math]e_2[/math] и [math]e_3[/math] имеют форму [math]r^n[/math] , [math]r^[/math] и [math]0[/math] , соответственно, для какого-то натурального [math]n[/math] . Это значит, что мы можем использовать увеличивающие пути [math]p_1[/math] , [math]p_2[/math] , [math]p_1[/math] и [math]p_3[/math] бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага [math]5[/math] равен [math]1 + 2(r^1 + r^2)[/math] . За бесконечное время полный поток сойдётся к [math]\textstyle 1 + 2\sum\limits_^\infty r^i = 3 + 2r[/math] , тогда как максимальный поток равен [math]2M + 1[/math] . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.

При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).

Алгоритм Форда-Фалкерсона позволяет найти максимальный поток в сети, который, в свою очередь, может быть использован при поиске максимального паросочетания в графе.

Реализация алгоритма

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

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

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

  • 3-4 обрабатывается случай, когда начальная и конечная вершины совпали (путь найден);
  • 5-7 обрабатывается ситуация, когда начальная вершина уже была посещена ранее (принадлежит списку visited ) — тогда путь нельзя найти. Для проверки используется функция find из модуля , которая принимает два итератора — на начальный и конечный элементы списка. Возвращает итератор на найденный элемент, а если не удалось найти — то итератор end() .
  • в строке 8 создается ссылка на список инцидентности начальной вершины.
  • в строках 9-17 перебираются все инцидентные ребра, при этом, в строках:
    • a) 10-11 пропускаются загруженные ребра, т.е. такие, по которым уже нельзя передать вещество;
    • b) 12 — текущее ребро добавляется в список помещенных;
    • c) 13-16 — запускается рекурсивный поиск из конца текущего ребра, если этот поиск удался (вернулось значение true ) — текущее ребро добавляется в начало ( push_front ) найденного пути.

    Этот алгоритм берет в графе список инцидентности для узла с номером src . Перебирает все его дуги до тех пор, пока не найдет дугу с концом в dst . Если такие дуги кончились — возвращает нулевой указатель.

    Теперь реализуем метод Форда-Фалкерсона:

    • создаются новые (пустые) списки для пути и посещенных вершин (строки 3-4);
    • выполняются поиск пути с помощью описанной выше функции dfs , если путь не найден — выходим из цикла (функция завершается — все потоки найдены);
    • величине min_flow присваивается единица, так как мы реализуем алгоритм для невзвешенного графа (пропускная способность все дуг равна единице). Для адаптации алгоритма ко взвешенному графу, необходимо выполнить поиск наименьшей остаточной пропускной способности дуг найденного пути;
    • для всех дуг — величина потока увеличивается на min_flow , находится антидуга, ее поток уменьшается на min_flow .

    Алгоритм поиска пути отработает за O(n) операций — в худшем случае он зайдет в каждую першину графа. Этот алгоритм будет запущен O(n) раз, так как в худшем случае в графе существует O(n) непересекающихся путей (из начальной вершины можно выйти не более чем n способами). Итого, асимптотическая сложность алгоритма в худшем случаем можно оценить как O(n*n).

    Применение алгоритма

    В задаче задается имя и набор кубиков, при этом каждый кубик связан с какими-то буквами имени. Можно построить из этого граф, представив каждый кубик узлом и каждую букву имени — тоже узлом. Дуги в графе — показывают возможность использования кубика для буквы имени.

    Однако, буквы имени имеют символ — добавим его в структуру узла графа. Узлы кубика не имеют символ (соответствующее поле в них хранит мусор) — их символы задаются списком инцидентности.

    Граф будет по определению двудольным, мы можем найти максимальное паросочетание в нем, при этом если размер паросочетания окажется равен количеству букв имени — значит возможно так использовать кубики, чтобы составить имя.

    Создадим граф, при этом считаем число кубиков и имя, определим количество символов в имени. Количество узлов в графе равно сумме длины имени с количеством кубиков:

    Тут char_to_id задает двумерный массив, в котором для каждой буквы имени хранятся ее номера. Например, имя "ANN" содержит две буквы N, для каждой из них будет создана своя вершина в графе — допустим, у этих вершин будут идентификаторы 2 и 3. Если на каком-то кубике будет буква N — то она должна быть связана с обоими буквами — для этого нам потребуются эти идентификаторы (2 и 3).

    Каждый кубик во входном файле задан строкой, в которой могли быть повторяющиеся символы. Однако каждый кубик может использоваться только один раз — поэтому повторяющиеся символы не имеют никакого смысла, их можно удалить. Удаление повторов в строке может занять O(N) операций, если для каждого символа выполнять поиск повторов, однако мы можем предварительно отсортировать символы строки — тогда сортировка отнимет O(N*log(N)) операций и выбор уникальных — еще N операций). В стандартной библиотеке С++ есть встроенный алгоритм unique , который удаляет идущие подряд повторы элементов, т.е. из "11221133" сделает 1213 . Если же ему на вход подать упорядоченную строку — то он удалит из нее все повторы. Такое применение этих алгоритмов описано в разборе другой олимпиадной задачи. В исходном коде это выглядит так:

    // обработка оставшихся символов строки: (дальше…)

    Теперь для оставшихся символов кубика установим связи с символами имени. Сделать это эффективно поможет массив char_to_id :

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

    Теперь, чтобы применить алгоритм Форда-Фалкерсона, добавим в граф вершины сток и исток и соединим их: сток с кубиками, а исток — с буквами имени:

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


    Формально понятие паросочетания вводится так: [1, стр. 514]: пусть дан граф G , состоящий из множества вершин V и множества ребег E . Подножество ребер E' является паросочетанием если среди вершин V нет вершины, инцидентной более чем одному ребру из E' .

    Более простым языком оно введено в [2, стр. 75]: паросочетание — это множество ребер, не имеющих общих концов (каждая вершина v из множества V является концом максимум одного ребра из множества V ).

    На практике чаще всего требуется искать максимальное паросочетание, т.е. такое, что количество ребер в нем максимально для данного графа.

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

    1. одно из множеств представляют работниками, а другое — заданиями. Дуги отражают способность работника выполнить задание. Максимальное паросочетание отражает наиболее полную загрузку работников задачами в данный момент [1];
    2. одно из множеств представляют мальчиками, а другое — девочками. Дуги — желание мальчиков и девочек танцевать друг с другом. Тогда максимальное паросочетание содержит максимальное количество пар, которые можно создать [3].

    Из этих примеров очевидно, что построение максимального паросочетания — это задача оптимизации (оптимальном распределении работников по задачам).

    В работе [3] отмечается, что паросочетания можно искать в произвольном графе, однако если для двудольного графа существуют алгоритмы с асимптотической оценкой сложности $$O(n^2)$$ и даже $$O(\sqrt\cdot m)$$, то для произвольного — не существует алгоритма, работающего быстрее чем за
    $$O(n^3)$$

    Практическое применение алгоритмов с такой вычислительной сложностью очень ограничено [1, стр. 55], тем не менее они существуют — например алгоритм Голдберга [4].

    Кроме того, в [1] описывается задача о паросочетаниях во взвешенном графе — в этой вариации необходимо выбрать не максимальное количество ребер, а паросочетание с максимальной (или минимальной) суммой весов ребер. Для решения такой задачи применяется венгерский алгоритм.

    В этой статье займемся изучением алгоритмов построения максимального паросочетания в невзвешенном двудольном графе.

    Общая постановка проблемы


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

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

    Области применения

    Приведенные выше примеры применения паросочетаний выглядят не очень полезными. Часто ли встает задача составить максимально число пар или переженить максимальное количество мужчин и женщин? Тем не менее, ряд задач сводится к поиску максимального паросочетания, например:

    Подходы к решению

    Использование потоков в сетях


    Понятие потока имеет смысл для сети, при этом граф рассматривается как сеть труб, по которым движется вещество. Исток — точка, в которой вещество производится с некоторой скоростью. Сток — точка потребления вещества с такой же скорость. Вес дуги определяет пропускную способностью трубы. Задача заключается в поиске максимальной допустимой скорости производства вещества. Классический метод решения этой задачи описан Фордом-Фалкерсоном, суть которого заключается в следующем:

    Формальное доказательство корректности подхода, а также доказательство его применимости к поиску максимальных паросочетаний приведены в [2, стр. 64-75], также в книге отмечается, что существует множество алгоритмов, реализующих этот метод — Эдмондса-Карпа, Карзанова и другие. Возможны реализации этого подхода как с помощью поиска в ширину [1, стр. 241-243], так и поиска в глубину [7].

    Использование чередующихся цепей

    Для такого алгоритма вводится следующая терминология:

    • цепь — путь в графе, не содержащий повторяющихся вершин;
    • чередующаяся цепь — это цепь, для любых двух соседних рёбер которой верно, что одно из них принадлежит паросочетанию , а другое нет.
    • дополняющая цепь (относительно паросочетания) — это чередующаяся цепь, начальная и конечная вершины которой не принадлежат паросочетанию.
    1. Просматривает все вершины первой доли графа.
    2. Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем.
    3. Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.

    Детальное изучения алгоритма, составление примеров

    Для реализации выбран метод Форда-Фалкерсона, так как он является более универсальным — позволяет не только искать максимальное паросочетание, но и вычислять поток в сетях. Также метод Форда-Фалкерсона применяют для поиска максимального разреза в графе [9].

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

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


    На следующем рисунке выделены дуги, добавление которых в сеть даст максимальный поток из вершины 1 в вершину 6. Для этого алгоритм должен был найти пути 1-2-4-6 и 1-3-5-6.


    Однако, что если первым найденным путем был 1-2-5-6? — Получится сеть, показанная ниже, видно, что второй путь из вершины 1 в вершину 6 найти не получится.



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

    Читайте также: