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) теперь снова применяются к новой матрице