4.1. Алгоритм для ЗН (случай минимизации)
Описанный здесь алгоритм был предложен Кёнигом [22], Эгервари [15] и Куном [23, 24] и известен как венгерский алгоритм.
4.1.1. Описание алгоритма
Присвоение начальных значений
Шаг 1. Вершинам из множеств
графа
присвоить веса
и соответственно, причем так, чтобы для любого ребра
выполнялось неравенство
Формирование графа
Шаг 2. Построить специальный остовный подграф
графа
с данными текущими весами
Построение дерева
Шаг 3. Если в
нет никакого альтернирующего дерева
то «выращивать» его, взяв в качестве корня некоторую экспонированную вершину
графа
принадлежащую множеству
если экспонированных вершин нет, то перейти к шагу 7. Если альтернирующее дерево уже существует, то продолжать «выращивать» его. Если дерево
окажется аугментальным, то перейти к шагу 4, а если венгерским — к шагу 5.
Аугменталъное дерево
Шаг 4. Улучшить текущее паросочетание, «взаимно поменяв» (вдоль аугментальной цепи) ребра, принадлежащие ему и ему не принадлежащие.
«Отбросить» дерево
и перейти к шагу 3.
Венгерское дерево
Шаг 5. Для ребер
не лежащих в
одна концевая вершина которых принадлежит текущему дереву
и помечена
как внешняя, а другая концевая вершина не принадлежит
найти
Шаг 6. Для каждой вершины
графа
принадлежащей
и являющейся внешней вершиной дерева
поменять
на
а для каждой вершины
графа
принадлежащей
и являющейся внутренней вершиной дерева
заменить
на
Сохранить дерево
и перейти к шагу 2.
Конец
Шаг 7. Текущее совершенное паросочетание является минимальным.
4.1.2. Матричная форма алгоритма
Часто, когда граф является полным, операции вышеприведенного алгоритма реализуются на
-матрице С, строки которой соответствуют вершинам из
а столбцы — вершинам из
Начальные элементы
являются стоимостями (весами) ребер
На шаге 1 алгоритма начальный вес
вершины
берется равным наименьшему элементу строки i. Вес
вычитается из всех элементов строки
и так делается для всех строк. Вес
вершины
берется равным наименьшему элементу в столбце к получившейся матрицы. Затем
вычитается из всех элементов столбца к, и
делается для всех столбцов, в результате чего получается новая матрица
. Матрица С называется редуцированной матрицей. Тогда остовным подграфом
будет
гсдвудольный граф с дугами (соединяющими только те вершины
для которых
Совершенное паросочетание графа
будет соответствовать такому выбору нулевых элементов в матрице С, когда в каждой строке и каждом столбце выбрано ровно по одному нулевому элементу С.
Построение альтернирующего дерева в зтом получившемся остовном подграфе
происходит с помощью следующей процедуры расстановки пометок в строках и столбцах матрицы С. Начнем построение произвольного паросочетания в
отмечая нулевые элементы в С так, чтобы никакие два отмеченные нуля не находились в одном и том же столбце или строке. (Если мы отметили нуль в позиции
то это означает, что ребро
входит в паросочетание, и наоборот.)
Найдем строку
без отмеченных элементов и сделаем пометку
Если такой строки нет, то текущее паросочетание будет минимальным совершенным паросочетанием.
если такая существует — соответствует теперь экспонированной вершине, выбранной в качестве корня альтернирующего дерева,
являются эквивалентами пометок, используемых для «хранения» этого дерева.) Это надо понимать так: дерево рассматривается как некоторая древовидность с корнем, причем если дуга
входит в эту древовидность, то «хранится равенство»
Для корня дерева мы берем
разд. 2.2.1, гл. 7.) Начинаем с такой ситуации, когда есть пометка
и когда все другие строки и столбцы не помечены.
(i) Пометить каждый непомеченный столбец к, содержащий неотмеченный
в помеченной строке
меткой
Если существует несколько возможностей, взять любую.
(ii) Пометить каждую непомеченную строку
содержащую отмеченный
в помеченном столбце к, меткой
Повторять процесс расстановки пометок (в соответствии с правилами
Эти две операции неявно строят в
дерево, причем это дерево дается эквивалентами пометок. Стоит заметить, что все «внешние» вершины этого дерева соответствуют строкам из С, а все «внутренние» — столбцам. Применение операций (i) и (ii) продолжается до тех пор, пока не будет помечен столбец
без отмеченных элементов (скажем, меткой
или процесс расстановки пометок нельзя будет продолжать. В первом случае будет найдена аугментальная цепь
где
Элементы
(нули) в позициях
матрицы С попеременно отмечаются или нет для образования лучшего паросочетания. Пометки
стираются, и процесс продолжается. Во втором случае обнаруживается венгерское дерево. Если
— множества всех помеченных, а
всех непомеченных строк и столбцов соответственно, то находим
(Заметим, что
Обновление.
для
для
для
А для
в остальных случаях
не изменяются. Операции (i) и (ii) теперь снова применяются к новой матрице