Задача присваивания: различия между версиями

<math>\forall x \in X \; \; \; \ell(x) = max_{y \in Y} \; w(x, y).</math>

Определим ''подграф равенства'', <math>G_{ \ell}\;</math>, как остовный подграф G, содержащий все вершины G и только те ребра (x, y), веса которых удовлетворяют условию <math>w(x, y) = \ell(x) + \ell(y) \;</math>.

'''Теорема 1. Если подграф равенства, <math>G_{ \ell}\;</math>, содержит совершенное паросочетание M*, то M* является в G паросочетанием с максимальным весом.'''

Вышеприведенная теорема служит основой алгоритма нахождения паросочетания с максимальным весом в полном двудольном графе. Начав с допустимой разметки, вычислим подграф равенства и затем найдем максимальное паросочетание в этом подграфе (на этом этапе веса ребер не учитываются). Если найденное паросочетание является совершенным, процесс на этом завершается. В противном случае к подграфу равенства добавляются ребра посредством пересмотра меток вершин. После добавления ребер к подграфу равенства либо увеличивается размер паросочетания (был найден дополняющий путь), либо продолжает расти [[венгерское дерево]]. В первом случае этот этап процесса завершается и начинается новый (поскольку размер паросочетания вырос). Во втором случае венгерское дерево растет за счет добавления к нему новых вершин, что, очевидно, не может произойти более n раз.

''(Структура венгерского дерева включает исследованные ребра при поиске базисного возможного решения одновременно из всех свободных вершин в S. Когда в T найдена вершина, сопоставленная какой-либо вершине из S, нужно исследовать только соответствующее ребро; однако в S исследуются все ребра, инцидентные этой вершине).''

Стоит отметить следующее свойство данного алгоритма: