Начнем со случайно выбранного паросочетания, т. е. случайно выберем некоторое множество нулей, никакие два элемента в котором не лежат в одной строке или столбце. Выбранные нули отмечены звездочкой. В строке 4 нет отмеченных элементов, и она получает пометку рстр 4 =0. Следующие пометки располагаются в таком порядке Рстолб З = 4, Ротр з = 3, Рстолб 7 = 3, Рстр 2 =

= 7. Окончательные векторы пометок [р^] и [р^] показаны справа от матрицы С и под ней.

Дальше помечать нечего. Теперь мы имеем I* = {2, 3, 4), К* = {3, 7}, I- = {1, 5, 6, 7, 8} и = {1, 2, 4, 5, 6, 8}. После вычисления А, которое равно 1, и после изменения весов [nj и [я;] получаем новую матрицу С = [с^ - nj - я], изображенную ниже;

Расстановка пометокпродолжается, так чтоРстолб 4=4 иРстолб s = = 2. Так как столбец 8 не имеет отмеченных нулей, то найдена аугментальная цепь, показанная стрелками в вышеприведенной матрице. Меняя отмеченные и неотмеченные нули вдоль этой цепи, получаем новое, улучшенное, паросочетание.

При второй итерации пометки стираются и в качестве строки 5ез отмеченных элементов выбирается строка 8, которая отмечается как Рстр 8 = 0. Больше пометок расставить нельзя, А оказы-

вается равным!, Лстрз заменяется на 6 и новая матрица С дана ниже. (Заметим, что при второй итерации венгерское дерево является на самом деле единственной изолированной - в терминах текущего графа G - вершиной, соответствующей строке 8.) Затем процесс расстановки пометок продолжается и получаются векторы [pi] и [ph], приведенные ниже.

Опять помечать больше нечего, Л оказывается равным 4, веса [лЛ и [ли\ изменяются и ниже дается новая матрица С (см. стр. 411).

Продолжается процесс расстановки пометок, и эти пометки <с учетом порядка их расстановки) таковы: Рстолб 5 = Рстолб т = Рстрв - 5, Рстрз=7,Рстолбб=6. Так как столбец 6 не имеет отмеченных элементов и он помечен, то найдена аугментальная цепь, показанная стрелками в матрице С. Изменяя вдоль этой цепи отмеченные и не отмеченные нули, получаем совершенное паросочетание, являющееся поэтому паросочетанием с минимальной стоимостью (весом). Ребра этого паросочетания таковы: (1, 1), (2, 8), (3, 7), (4, 5), (5, 2), (6, 6), (7, 4) и (8, 3), а полная стоимость (вес) равна 76 (для проверки заметим, что S Ц- S ft = 76).

5. Общая задача построения остовного подграфа с предписанными степенями

Для заданного графа G = {X, А), дугам которого приписаны гоимости, общая задача была сформулирована во введении как адача нахождения остовного подграфа Gp, по отношению к кото-ому степени вершин xi равны заданным целым числам и сум-а стоимостей ребер в Gp максимальна (или минимальна). Во вве-ении отмечалось, что ЗМП является частным случаем этой общей гдачи. Теперь мы покажем, что общая задача сама может быть ешена как ЗМП с использованием алгоритма из разд. 3.1.1.

Исходя из графа G, построим граф G. Если требуется, чтобы i было степенью вершины xi в графе G, то в G будут сопоставлены ершине Xi bi вершин 4, а^?, , х\\ Каждому ребру а^ = {xi, It) графа G будут соответствовать в G две дополнительные вершины

и Sj, ребра {xf, rj), а = 1, . . ., б^, все со стоимостями у с^,

ебра {Sj, а|), Р = 1, . . ., б^, со стоимостями ус и ребро j, Sj) со стоимостью 0.