Лекции - Структуры и алгоритмы компьютерной обработки данных / 21.Построение максимального паросочетания в двудольном графе

Сведение к максимальному потоку

• Сеть с несколькими истоками и стоками. Задача сводится к стандартной добавлением фиктивного истока, связанного с истоками, и фиктивного стока, связанного со стоками.

• Пропускная способность вершины. Такая вершина удваивается по следующей схеме:

Максимальное паросочетание в двудольном графе

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

Сведение к максимальному потоку

Добавим исток, соединив его со всеми вершинами первого множества, и сток, соединив со всеми вершинами второго. Пропускные способности ребер = 1. Найдем максимальный поток. Насыщенные ребра в потоке образуют паросочетание. Сложность O(mn).

Венгерский алгоритм (метод чередующихся цепей)

Пусть М— паросочетание в двудольном графе.

Чередующейся относительно М цепью называется цепь x1-x2-x3-…-xn, удовлетворяющая следующим условиям

1.

2. Нечетные ребра x1-x2, x3-x4,… не принадлежат M

Четные ребра x2-x3, x4-x5,… принадлежат M.

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

Отсюда алгоритм: пока в графе существует чередующаяся цепь, увеличиваем паросочетание вдоль нее. Поиск цепи можно производить поиском в глубину или в ширину. Во втором случае получается сложность O(n2.5).

Процедура поиска паросочетания

A[1..n, 1..m] – граф (n вершин в первой доле, m - во второй).

V[1..n] – отметка о посещении вершины

P[1..m] – паросочетание

function Tr (x: longint): boolean;

Var i: longint;

begin

Tr:=False;

if not(V[x]) then

begin

V[x]:=true;

for i:=1 to M do

if (A[x,i]=1) and ((p[i]=0) or Tr(P[i]))

then begin Tr:=True; P[i]:=x; break

end;

end;

end;

for i:=1 to M do P[i]:=0;

for i:=1 to N do

begin

for j:=1 to N do V[j] := False;

Tr(i);

end;