Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей
Шаг 0. По матрице данного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером (ij) поместим символ «´» и назовем ее недопустимой, если в матрице двудольного графа ; если же , то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.
Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ «1». Если в первой строке все клетки недопустимы, то перейдем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поставим «1». Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом «1» в третьей строке. Если окажется, что во всей таблице все клетки недопустимы, то на этом все действия заканчиваются и выдается ответ: «в графе нет ребер». Если же все-таки удастся поставить первую «1», то после этого просмотрим все остальные строки таблицы в порядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева направо и фиксируем первую по ходу просмотра допустимую клетку такую, которая является независимой по отношению к допустимым клеткам, в которых уже стоит символ «1», и проставляем в эту клетку «1», после чего переходим к тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице символам «1». (Под ребром, соответствующим символу «1» в рабочей таблице, подразумевается следующее: если «1» стоит в клетке с номером (ij), то соответствующим будет ребро ) Легко заметить, что этот набор ребер - максимальное паросочетание.
Если в результате проведения всех действий на этом шагу в каждой строке рабочей таблицы окажется символ «1», то ребра из указанного только что паросочетания и составляют наибольшее паросочетание, и действия окончены. Если же в результате проведения первого шага остались строки без «1», то пометим их справа от таблицы символом «*» переходим к следующему шагу.
Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Просмотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматриваемой строки. При этом соблюдается принцип (Ã): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей.
Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющееся паросочетание (полученное на Шаге 1) является искомым наибольшим и все действия прекращаются. Если же среди столбцов появятся помеченные, то переходим к следующему шагу.
Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскивается символ «1» и строка, в которой он расположен, помечается номером просматриваемого столбца.
Физически пометки выставляются справа от таблицы, на уровне соответствующих строк. Всегда соблюдается принцип (Ã).
Если в результате действий по этому шагу возникнет ситуация, когда в просматриваемом столбце нет символа «1», то действия на данном шагу прерываются и надо перейти к следующему шагу - Шагу 4. Если же в результате действий по этому шагу будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк (одни будут помечены символом «*», другие - номерами столбцов), то следует вернуться к Шагу 2 и повторить предусмотренные им действия.
Если в результате этих действий по Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавливается. Если же среди помечаемых столбцов возникнут новые помеченные столбцы, то следует повторить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возникнет новых помеченных строк, то это означает, что имеющееся паросочетание является искомым.
Шаг 4. Рассматривается столбец, имеющий пометку и не содержащий символа «1». Мы сейчас изменим набор символов «1», расположенных в рабочей таблице.
В рассматриваемый столбец поставим символ «1» в строку, номер которой равен пометке этого столбца. Затем в этой строке отыщем «старый» символ «1» и переместим его по его столбцу в строку, номер которой равен пометке при этом столбце. (Можно доказать, что описанное действие реально всегда осуществимо.) Затем в строке, куда попал последний символ «1» отыщем «старый» символ «1» и с ним проделаем то же самое. В конце концов очередной перемещаемый «старый» символ «1» окажется в строке, где больше символов «1» нет. Возник новый набор символов «1», в котором уже элементов на один больше, чем в исходном наборе символов «1». По этому новому набору можно построить паросочетание так же, как это делалось в самом начале и после этого повторить все сначала.
В конце концов возникнет одно из указанных выше условий прекращения действий по алгоритму и наибольшее паросочетание будет найдено.
Пример 12.1. Найти наибольшее паросочетание в следующем двудольном графе со следующей матрицей:
Сам двудольный граф в этом примере выглядит так:
Будем проводить шаг за шагом описанный выше алгоритм. Рабочая таблица:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
9
x
x
x
x
x
x
метки
Выполняем первый шаг 1: расставляем независимые единицы и отмечаем строки, в которые единицы не попали:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Паросочетание, которое соответствует выбранным единицам: ; ; ; ; ; ; .
Далее шаг 2, столбцы допустимых клеток помеченных строк пометим номерами этих строк, следуя принципу (Ã):
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Далее шаг 3, в помеченных столбцах отыщем единицы и их строки пометим номерами их столбцов:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Теперь снова шаг 2, пометим столбцы, отправляясь от помеченных строк и соблюдая принцип (Ã):
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Теперь снова шаг 3, просмотрим помеченные столбцы и пометим строки:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Теперь снова шаг 2, пометим столбцы (при принципе (Ã)):
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Теперь снова шаг 3 – просмотр столбцов и ищем «1», но в столбце №5 с меткой 4 нет «1»: Следовательно, можно набор единиц можно увеличить на одну - шаг 4: новые единицы – выделены жирным курсивом, старые зачеркнуты:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
1
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
1
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
*
метки
Мы получили новый набор независимых единиц:
yx
1
2
3
4
5
6
7
8
9
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
9
x
x
x
x
x
x
Теперь вся процедура повторяется сначала, Шаг 1- единственная пометка «*» у строки №8. Шаг 2 - пометим столбцы допустимых клеток этой строки ее номером:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
метки
Затем шаг 3 - в помеченных столбцах найдем единицы и их строки пометим номерами столбцов:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
метки
Шаг 2:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
метки
Шаг 3:
yx
1
2
3
4
5
6
7
8
9
метки
1
x
x
x
x
x
x
2
x
x
x
x
x
x
3
x
x
x
x
x
x
4
x
x
5
x
x
x
x
x
x
6
x
x
x
x
x
x
7
x
x
x
8
x
x
x
x
x
x
*
9
x
x
x
x
x
x
метки
Сложилась ситуация, когда расстановка пометок «зациклилась». Это означает, что искомое паросочетание состоит из ребер, соответствующих проставленным единицам, т.е. ; ; ; ; ; ; ;.
данного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером (ij) поместим символ «´» и назовем ее недопустимой, если в матрице двудольного графа 
; если же 
, то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.
) Легко заметить, что этот набор ребер - максимальное паросочетание.
; 
; 
; 
; 
; 
; 
.
; 
; 
; 
.