Задача о наибольшем паросочетании в двудольном графе Автор: Воробьева Елена vorobeva@rain.ifmo.ru 2002 год. - презентация

1 Задача о наибольшем паросочетании в двудольном графе Автор: Воробьева Елена 2002 год

2 Граф G=(M,N) называется простым или двудольным, если множество его вершин разбито на два множества M е и M b, и все начала дуг принадлежат M b, а все концы M е, т.е. M = M eM b, M eM b =, eN: e=(i,k), iM b, kM e c неповторяющимися i и k.

3 Набор дуг J N называется паросочетанием, если для любых j 1, j 2 J, j 1 j 2, начала и концы этих дуг различны: beg j 1 beg j 2, end j 1 end j 2. Рассмотрим далее построение паросочетания, максимального по числу входящих дуг.

4 Мы будем использовать метод Форда-Фалкерсона для поиска максимального паросочетания в двудольном графе G=(M,N). Для этого рассмотрим сеть G' = (M,N'), соответствующую двудольному графу G. Эта сеть строится так: добавляются две новые вершины, которые будут истоком (s) и стоком (t): M = M {s, t}. Множество (направленных) рёбер сети G' таково: N' = {(s,u): uM b } {(u,v): uM b, vM e, (u,v)N} {(v,t): vM e } (напомним, что через M b и M e обозначаются доли графа). Будем считать, что пропускная способность каждого ребра равна единице. Построение наибольшего паросочетания с помощью максимального потока в сети.

5 Алгоритм построения паросочетания: 1.соединяем s дугами с i M b 2.соединяем t дугами с j M e 3.направление на ребрах устанавливаем от i к j 4. ( i, j ): C ij = 1 5.методом Форда-Фалкерсона ищем максимальный поток. Насыщенные ребра потока соответствуют наибольшему паросочетинию исходного графа. Рассмотрим пример:

6 Сеть G и максимальный поток в ней. Пропускная способность любого ребра равна 1. Поток по фиолетовым ребрам равен единице, по остальным – нулю. Построив максимальный поток через эту сеть, насыщенные ребра будут соответствовать наибольшему паросоче- танию в графе.

7 Следующая лемма устанавливает соответствие между потоками в G и паросочетаниями в G. Поток f в сети G называется целочисленным, если все значения f(u,v) = целые. Метод Форда-Фалкерсона всегда дает целочисленный максимальный поток, если только пропускная способность всех ребер целые числа (на каждом шаге, при каждом добавлении потока по дополняющему пути, поток остается целочисленным ). Лемма. Пусть G = (M,N) – двудольный граф с долями M b и M e, и G`=(M`,N`) – соответствующая сеть. Пусть J – паросочетание в G. Тогда существует целочисленный поток в G` с величиной |f| = |J|. Обратно, если существует целочисленный поток в G, то в G найдется паросочетание с |f| рёбрами. Доказательство. Сначала докажем, что паросочетание порождает поток, задав поток f следующим образом. Если (u,v) J, то f(s,u) = f(u,v) = f(v,t) = 1 f(u,s) = f(u,v) = f(t,v) = -1

8 Для всех остальных рёбер (u,v) N` положим f(u,v) = 0. Иначе говоря, каждое ребро (u,v) J соответствует единичному потоку по пути suvt. Никакие два таких пути не содержат общих вершин (кроме истока и стока) или рёбер. Чтобы проверить, что f является потоком, достаточно заметить, что f представим в виде суммы потоков по этим путям. Поток через разрез (M b{s} = S, M e{t} = T) равен |J| |J|=f(S,T)=f(S,M)–f(S,S) = f(S,M)=f(s,M) + f(S\s,M)= f(s,M) = |f| поэтому величина потока |f| равна |J|. Докажем обратное. Пусть f – целочисленный поток в G; его значения на рёбрах могут быть равны 0 или 1, так как пропускная способность рёбер ограничена единицей. Определим J = {(u, v) : u M b, v M e, f(u, v) = 1} Докажем, что J – паросочетание. В самом деле, из одной вершины u не могут выходить два ребра (u,v) и (u,v), по которым поток равен 1, т.к. входящий в u поток не превосходит 1. По аналогичным причинам в любую вершину v входит не более одного ребра с единичным потоком.

9 Убедимся, что |J| = |f|. Заметим, что |J| есть поток через разрез (M b{s}, M e{t}) (по каждому ребру паросочетания идёт поток 1, а число рёбер есть |J|). Таким образом лемма сводит задачу о максимальном паросочетании к задаче о целочисленном максимальном потоке.

10 Рассмотрим еще один вариант постановки этой задачи. Обозначим существующие ребра матрицей A, где строки соответствуют M e, а столбцы M b : Введем неизвестную величину: Помимо (1) величина x ij удовлетворяет еще двум условиям: Построение наибольшего паросочетания методом чередующихся цепей.

11 Чтобы было как можно большее паросочетание, надо максимизировать функционал: Запись задачи состоит из оптимизируемого линейного функционала и нескольких условий (называемых ограничениями), которые линейны, как (2) или (3). Такая задача называется задачей линейного программирования.

12 Для решения задачи о наибольшем паросочетании применяется метод чередующихся (или удлиняющихся) цепей. Пусть J - паросочетание в двудольном графе G. Цепь, в которую поочередно входят ребра из J и не из J назовем чередующейся (удлиняющейся) относительно J. По определению, цепь, состоящая из одного ребра, тоже чередующаяся. Вершины, инцидентные ребрам из J назовем насыщенными, а прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно J цепь с ненасыщенными концевыми вершинами, то в ней ребер, не принадлежащих паросочетанию, на одно больше, чем принадлежащих. Если цепь «перекрасить», т. е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание, увеличатся на одно ребро. Чередующаяся относительно J цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно J цепью.

13 Теорема 1. Паросочетание J является наибольшим тогда и только тогда, когда нет увеличивающих относительно J цепей. Доказательство. Необходимость очевидна, а достаточность докажем от противного. Пусть увеличивающихся относительно J цепей нет, а большее, чем J, паросочетание Jо есть. Рассмотрим граф Н, состоящий из ребер, входящих или в J, или в Jо, но не в оба вместе. Вообще, Н необязательно связный, и в нем ребер из Jо больше, чем ребер из J. Любая вершина H инцидентна самое большее одному ребру из J и одному из Jо. Связная компонента из Н может быть: 1. циклом; 2. цепью, у которой одно концевое ребро из J, а второе из Jо; 3. цепью, у которой оба концевых ребра из J; 4. цепью, у которой оба концевых ребра принадлежат Jо.

14 Цикл в двудольном графе, очевидно, имеет четное число ребер, значит, в случае (1) число ребер из J равно числу ребер из Jо. То же соотношение верно для случая (2), а в случае (3) ребер из J больше, чем ребер из Jо. Но в графе Н ребер из Jо больше, чем из J, поэтому обязательно должен быть случай (4). Но цепь в этом случае является увеличивающей относительно J, что даст противоречие, доказывающее теорему. Теорема 1 служит основой для алгоритма нахождения наибольшего паросочетания. Но прежде, чем описывать этот алгоритм, мы выделим вспомогательный алгоритм перечисления всех вершин ориентированного графа, достижимых из данной вершины. В алгоритме данная вершина - s, результат (в виде номера предыдущей вершины на пути достижения) записывается в массиве Р из n чисел, где n - количество вершин графа; еще используются рабочие массив boolean R (из n элементов) и очередь обрабатываемых элементов Q.

15 Алгоритм 1: Перечисление вершин орграфа, достижимых из s 1.(инициализация): prev:= s, для i = 1,…,n все R[i]:=false, P[i] := (общий шаг): 2.1. в цикле рассмотрим все вершины k в орграфе, непосредственно следующие за prev. Если для вершины k R[k] = false, то enqueue(Q,k); P[k] := prev; R[k] := true Если Q !=, то prev = dequeue (Q); перейти к (завершение): выдача Р, конец.

16 Рассмотрим пример: (дан ориентированный граф, найти все вершины, достижимые из s=1) шаг 1 : все P и R равны -1 и false; prev := 1; Q := шаг 2.1 : Q = {2} P = (-1, 1,-1, …) R = (f, t, f,…) шаг 2.2: Q = {} prev = 2; шаг 2.1 : Q ={3, 4} P = (-1, 1, 2, 2, -1, -1, -1) R = (f, t, t, t, f,…) (вершины 3 и 4 включены в рабочую зону Q, в P отмечено, что они достижимы из 2, в R мы отмечаем, что их уже посетили )

17 шаг 2.2: Q = {4} prev = 3 шаг 2.1: Q = {4} P = (-1,1,2,2,-1,-1,-1) R – не изменился, т.к. после рассмотрения вершины 3 множество достижимых вершин не изменилось шаг 2.2: Q = {5} prev = 4 шаг 2 : Q = {5} P = (-1,1,2,2,4,-1,-1) R[5] = true (мы достигли 5-ой вершины) шаг 2: Q = {} P = (-1,1,2,2,4,-1,-1) новых достижимых вершин нет шаг 3:завершение Массив Р можно «раскрутить» и узнать, по какому пути (кратчайшему по числу шагов) достижима каждая вершина. Скажем, массив Р показывает, что вершина 5 достижима из 4, 4 из 2, 2 из 1, т.е. существует путь [1,2,4,5].

18 Теперь вернемся к описанию алгоритма нахождения наибольшего паросочетания. Пусть I={1,2,...,m} - номера верхних вершин, а K={1,2,...,n} - - номера нижних. Вначале все вершины ненасыщенные. Для построения начального паросочетания применим «жадный» алгоритм; будем просматривать по очереди вершины из I, если из i I ведут ребра в ненасыщенные вершины из K будем жадно хватать и вводить в паросочетание первое попавшееся ребро, не думая о последствиях. Далее, преобразуем двудольный граф В в ориентированный граф В, введя ориентацию следующим образом: все ребра, вошедшие в J, ориентируем снизу вверх, т.е. из K в I, а остальные ребра сверху вниз, т.е. из I в K. Пусть I = I + I -, K = K + K -, где минус означает подмножество ненасыщенных ребер, а плюс насыщенных. Очевидно, что увеличивающая относительно паросочетания J цепь существует в графе В тогда и только тогда, когда в графе B существует путь из s в t, где s I -, t K -.

19 Алгоритм 2: построение наибольшего паросочетания 1.(инициализация): 1.1. Построение начального J (производится описанным выше «жадным» алгоритмом) Построение ориентированного графа В (описано выше). 2. (общий шаг): 2.1. В цикле по i I - применить алгоритм 1 нахождения всех вершин В, достижимых из вершины I -. Если среди достижимых вершин окажется вершина k oK -,то (i,...,kо) есть увеличивающая относительно J цепь в графе B. Увеличить J и перейти к (завершение): выдача J, конец.

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

21 На рисунке I - ={4}. Из вершины 4 в графе В достижимы вершины 1', 2, 3, 4' и 4'. Вершина 4 K -. Строится путь [4, 3', 3, 1', 2, 4']. В соответствующей увеличивающей цепи в графе В меняется цвет ребер. Полученное наибольшее паросочетание показано на следующем рисунке.

22 Список используемой литературы: 1.И.В.Романовский Дискретный анализ 2.Т.Кормен, Ч.Лейзерсон, Р.Ривест Алгоритмы построение и анализ 3.В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко Основы программирования