Пример №28.
Построить увеличивающую цепь для паросочетания, приведенного в табл. 7.1. Расстановка меток приведена в табл. 7.2. Метки строк и столбцов показаны курсивом с подчеркиванием.
Шаг 1. Метим строки 8 и 9 меткой 0.
Шаг 2. Метим столбцы с номерами 2, 4, 6 меткой 8, а столбцы с номерами 1 и 8 — меткой 9.
Шаг 3. Строки 1, 2, 3, 6 получают метки 2, 1, 4, 8 соответственно.
Шаг 2. Столбец 3 получает метку 2.
Шаг 3. Строка 4 получает метку 3.
Шаг 2. Столбцы 5 и 9, помеченные от четвертой строки, не содержат кружков (табл. 7.2).
Шаг 5. Возьмем в качестве одной из открытых вершин увеличивающей цепи или вершину 5, или вершину 9 (из множества 
), например, вершину 5. Выделим увеличивающую цепь. Столбец 5 помечен от строки 4, строка 4 — от столбца 3, столбец 3 — от строки 2, строка 2 — от столбца 1, столбец 1 — от строки 9. Эта строка помечена нулем. Определена вторая открытая вершина увеличивающей цепи (из множества 
). Сама цепь такова (жирным шрифтом выделены ребра из паросочетания): (9,1), (2,1), (2,3), (4,3), (4,5).
Исключим ребра (2, 1) и (4, 3) из паросочетания, включим в паросочетание ребра (9, 1), (2, 3), (4, 5); общее число ребер в нем увеличилось на единицу (табл. 7.3).
Можно ли добавить к найденному паросочетанию еще одно ребро? Выполним снова шаги 1—4 (см. табл. 7.3). Ни одной новой метки приписать нельзя, а все помеченные столбцы содержат кружки. Следовательно, паросочетание в табл. 7.3 — наибольшее.
То, что данный алгоритм действительно находит увеличивающую цепь, если она существует, вытекает из его описания. Докажем, что в случае б) шага 4 непомеченные строки и помеченные столбцы образуют минимальное покрывающее множество рядов. Имеем:
1) ни одна единица не может стоять в помеченной строке и непомеченном столбце (см. шаги 1, 2, 3);
2) общее число кружков равно сумме помеченных столбцов и непомеченных строк. Действительно, все помеченные столбцы содержат кружки, а все кружки, стоящие в непомеченных строках, стоят одновременно в непомеченных столбцах (шаг 3).
В табл. 7.3 непомеченные строки 2, 4, 7, 9 и помеченные столбцы 2,4, 6, 8 образуют минимальное покрывающее множество рядов. Всего имеем 8 ребер в наибольшем паросочетании и 8 строк и столбцов в этом покрывающем множестве.
Эта задача взята со страницы решения задач по предмету «линейное программирование»:
Решение задач по линейному программированию
Возможно эти страницы вам будут полезны:
