Алгоритм использует для построение паросочетания так называемый метод чередующихся цепочек. Начнём строить наше паросочетание, последовательно прибавляя к нему всё больше и больше рёбер, пока не придём к ситуации, что текущее паросочетание максимально и больше добавить рёбер нельзя. Покрасим рёбра, входящие в текущее паросочетание в зелёный цвет. Рёбра, не входящие в текущее паросочетание покрасим в чёрный цвет. Изначально в графе все рёбра чёрные, т.к. мы ещё не начинали строить паросочетание.
Назовём вершину графа свободной, если из неё не выходит зелёных рёбер. Назовём некоторый простой путь из рёбер с цветами чёрное-зелёное-...-чёрное чередующейся цепочкой, если первая и последняя его вершины свободны.
Теперь будем делать следующее: находим любую чередующаяся цепочку и перекрашиваем все её рёбра в противоположный цвет. Очевидно, что впоследствии такого действия количество зелёных рёбер увеличится на один, а их множество по-прежнему будет задавать некоторое (пока, возможно, не максимальное) паросочетание. Так делаем до тех пор, пока все чередующиеся цепочки не повыведутся. Утверждение: к этому моменту множество зелёных рёбер будет задавать максимальное паросочетание.
Теперь вся проблема свелась к тому, как искать чередующиеся цепочки. В качестве потенциального начала следующей цепочки будем перебирать последовательно все вершины одной из долей графа, а потом пытаться найти цепочку, выходящую из этой вершины. Для успешного проведения подобных действий нам понадобится дополнительный массив меток Use: array[0..MaxX] of Boolean и массив P: array[1..MaxY] of Integer, в котором мы будем хитрым образом хранить текущее состояние "зелёности" рёбер.
Действительно, как нам лучше хранить информацию о зелёных рёбрах, в данный момент присутствующих в графе? Можно, конечно, в матрице смежности двудольного графа хранить не True и False в зависимости от наличия ребра, а хранить, скажем, 0 для отсутствия ребра, 1 для чёрного и 2 для зелёного ребра. Но это неудобная и неоптимальная фишка, забейте на неё.
Чтобы придумать более хитрый метод хранения, надо сначала слегка подумать, а потом заметить вот что: из одной вершины может выходить не более одного зелёного ребра. Действительно, если из одной вершины выходит два зелёных ребра, то они однозначно смежны, что противоречит понятию паросочетания. Таким образом мы можем сделать следующее: будем хранить 0 в элементе массива P[I], если из I-ой вершины одной доли не выходит зелёных рёбер, а если зелёное ребро выходит в вершину с номером K другой доли, то положим P[I] равным K. И вот ещё что: для реализации алгоритма нам понадобится массив P лишь для вершин второй доли, поэтому его размерность равна MaxY. Таким образом, если, скажем, P[1] = 3, это значит, что из первой вершины второй доли выходит зелёное ребро в третью вершину первой доли.
Ниже приведён фрагмент программы, реализующей алгоритм Куна (здесь I: Integer).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Function Find(V: Integer): Boolean; Var I: Integer; Begin Use[V] := True; For I := 1 to Y do If A[V, I] and not Use[P[I]] and ((P[I] = 0) or Find(P[I])) Then Begin P[I] := V; Find := True; Exit; End; Find := False; End; ... For I := 1 to X do Begin FillChar(Use, SizeOf(Use), False); Find(I); End; |
Функция Find(V) возвращает False, если ей не удалось найти чередующаяся цепочку, начинающуюся в вершине V первой доли, а если удалось, то она возвращает True и инвертирует цепочку. Изначально P[I] = 0 для всех I от 1 до X. Утверждение: если запустить функцию Find по порядку из всех вершин первой доли, будут найдены все чередующиеся цепочки, т.е. мы построим максимальное паросочетание. В цикле, начинающемся в строке 13, обнуляется массив меток в строке 14, а в строке 15 запускается очередная функция Find.
Рассмотрим теперь работу функции. Запустившись из вершины V, она в строке 4 помечает её, чтобы в дальнейшем к ней уже не обращаться (повторное обращение может возникнуть из-за рекуррентности функции). Далее в строке 5 запускается цикл, в котором она пытается найти первое ребро чередующейся цепи. Если оно выходит в вершину I второй доли, то оно должно удовлетворять следующим условиям (строка 6): во-первых, оно должно существовать :) (условие A[V, I]). Во-вторых, если из его вершины во второй доле (I) выходит зелёное ребро, то другая вершина этого зелёного ребра в первой доле должна быть ещё не помечена (условие not Use[P[I]]). И если это всё так, то или вершина I во второй доле свободна (условие P[I] = 0), или из другой вершины выходящего из неё зелёного ребра мы можем построить продолжение чередующейся цепочки (условие Find(P[I])). Если P[I] = 0, то условие not Use[P[I]], не нужное в данном случае, автоматом даст True (т.к. в нулевом элементе массива Use всегда хранится False), и не повлияет на итоговое значение выражения.
Если условие выполнилось, мы инвертируем текущее звено цепи в строке 7. Один стековый экземпляр функции, как Вы уже могли заметить, отвечает за поиск лишь одной пары рёбер чёрное-зелёное; если для вершины I второй доли P[I] = 0, значит ребро {V, I} замыкает цепь. В строке 8 мы говорим, что чередующаяся цепочка найдена, а в строке 9 завершаем текущий экземпляр функции.
Если ни из одной смежной вершины второй доли нам не удалось продолжить цепочку, выполняется присваивание в строке 11, в котором мы говорим, что всё плохо, и цепочка не найдена, после чего функция, опять же, завершает работу.
Найденное максимальное паросочетание можно вычленить из массива P. Количество ненулевых элементов массива будет соответствовать мощности паросочетания.