как внешняя, а другая концевая вершина не принадлежит Т, найти

А = min {Cj - я? - п\].

Шаг 6. Для каждой вершины графа G, принадлежаш,ей Х' и являющейся внешней вершиной дерева Т, поменять nf на я? + А, а для каждой вершины графа G, принадлежащей Х^ и являющейся внутренней вершиной дерева Т, заменить

на Яь -А.

Сохранить дерево Т и перейти к шагу 2. Конец

Шаг 7. Текущее совершенное паросочетание является минимальным.

4.1.2. Матричная форма алгоритма

Часто, когда граф является полным, операции вышеприведенного алгоритма реализуются на (п X ге)-матрице С, строки которой соответствуют вершинам из X , а столбцы - вершинам из X. Начальные элементы с^ являются стоимостями (весами) ребер (xi, Xk).

На шаге 1 алгоритма начальный вес я? вершины Xi 6 X* берется равным наименьшему элементу строки i. Вес я вычитается из всех элементов строки i, и так делается для всех строк. Вес вершины Xk € X берется равным наименьшему элементу в столбце к получившейся матрицы. Затем вычитается из всех элементов столбца к, и зто делается для всех столбцов, в результате чего получается новая матрица С с cJh = с^ь - я? - Щ. 0. Матрица С называется редуцированной матрицей. Тогда остовным подграфом G будет {п X ге)-двудольный граф с дугами (Xi, Xk), соединяющими только те вершины Х{ и Xk, для которых cik = О- Совершенное паросочетание графа G будет соответствовать такому выбору нулевых элементов в матрице С, когда в каждой строке и каждом столбце выбрано ровно по одному нулевому элементу С.

Построение альтернирующего дерева в зтом получившемся остовном подграфе G происходит с помощью следующей процедуры расстановки пометок в строках и столбцах матрицы С. Начнем построение произвольного паросочетания в G, отмечая нулевые элементы в С так, чтобы никакие два отмеченные нуля не находились в одном и том же столбце или строке. (Если мы отметили нуль в позиции (i, к), то это означает, что ребро {xi, Xk) входит в паросочетание, и наоборот.)

1) См. примечание 2 на стр. 382.- Прим. ред.

Найдем строку s без отмеченных элементов и сделаем пометку Ра = 0. Если такой строки нет, то текущее паросочетание будет минимальным совершенным паросочетанием. (Вершина - если такая существует - соответствует теперь экспонированной вершине, выбранной в качестве корня альтернирующего дерева, а Pi являются эквивалентами пометок, используемых для хранения этого дерева ).) Это надо понимать так: дерево рассматривается как некоторая древовидность с корнем, причем если дуга (а> в) входит в эту древовидность, то хранится равенство Рр = Ха- Для корня дерева мы берем = 0. (См. разд. 2.2.1, гл. 7.) Начинаем с такой ситуации, когда есть пометка р^ = О и когда все другие строки и столбцы не помечены.

(i) Пометить каждый непомеченный столбец к, содержащий неотмеченный О в помеченной строке i, меткой р^ = i. Если существует несколько возможностей, взять любую.

(ii) Пометить каждую непомеченную строку i, содержащую отмеченный О в помеченном столбце к, меткой Pi = к.

Повторять процесс расстановки пометок (в соответствии с правилами (]) и (ii)). Эти две операции неявно строят в G дерево, причем это дерево дается эквивалентами пометок. Стоит заметить, что все внешние вершины этого дерева соответствуют строкам из С, а все внутренние - столбцам. Применение операций (i) и (ii) продолжается до тех пор, пока не будет помечен столбец t без отмеченных элементов (скажем, меткой pt) или процесс расстановки пометок нельзя будет продолжать. В первом случае будет найдена аугментальная цепь t, pt, pv, pr, s, где t = Pi, t = Pi и т. д. Элементы О (нули) в позициях {t, pt), iPti Pv), (Pt-i Pt ), { > матрицы С' попеременно отмечаются или нет для образования лучшего паросочетания. Пометки Pi стираются, и процесс продолжается. Во втором случае обнаруживается венгерское дерево. Если I* ж К* - множества всех помеченных, а 7 и К~ - всех непомеченных строк и столбцов соответственно, то находим

Д = т1п [clft].

(Заметим, что cltt = Ci - я? - л^.)

Обновление. = Яг -- Д для iI*, Яй = Яй - А для к^К*, ск-=с'ги - ДЛЯ i 6 /- и А; 6 К-, с[и = с'гУ Д^* i 1- жк Ю , в остальных случаях сш не изменяются. Операции (i) и (ii) теперь снова применяются к новой матрице С и т. д.

4.2. Пример

Решим ЗН для полного двудольного rj матрица С стоимостей (весов) такая:

[)а G = 8,8, где

Редуцированной матрицей С будет (8х 8)-матрица, приведенная ниже, где векторы слева ov матрицы и вверху - весовые векторы [jii] и [яь1 соответственно.