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

Пусть дан [[полный граф|полный]] [[двудольный граф]] <math>G = (X, Y, X \times Y) \;</math> с присвоенным каждому ребру (x, y) весом w(x, y). [[Паросочетание]] M представляет собой подмножество ребер, такое, что никакие два ребра в M не имеют общей вершины. Паросочетание является [[совершенное паросочетание|совершенным]], если в него входят все вершины. Предположим, что |X| = |Y| = n. Задача поиска паросочетания на взвешенных двудольных графах заключается в нахождении паросочетания с максимальным общим весом, где <math>w(M) = \sum_{e \in M} w(e) \;</math>. Поскольку граф G является полным и двудольным, у него имеется совершенное паросочетание. Алгоритм для решения данной задачи предложили Кун [4] и Манкрес [6]. Будем предполагать, что всех веса ребер неотрицательны.

Заметим, что сумма меток является верхней границей веса паросочетания с максимальным весом. Алгоритм последовательно находит паросочетание и допустимую разметку, такие, что вес паросочетания оказывается равен сумме всех меток.

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

Поскольку метки в S уменьшаются, ребра (в графе G), ведущие из S в <math>\bar{T}</math>, потенциально могут попасть в подграф равенства <math>G_{ \ell}\;</math>. По мере увеличения значения <math>\lambda \;</math> в какой-то момент ребро окажется в подграфе равенства. В этот момент процесс следует остановить и обновить венгерское дерево. Если вершина из <math>\bar{T}</math>, добавленная к T, сопоставлена с вершиной из <math>\bar{S}</math>, обе эти вершины перемещаются в S и T, что увеличивает размер венгерского дерева. Если вершина из <math>\bar{T}</math> свободна, то дополняющий путь найден и данный этап завершен. Этап состоит из таких шагов, выполненных между приращениями размера паросочетания. Поскольку в G всего n вершин, у алгоритма будет не более n этапов, поскольку на каждом этапе размер паросочетания увеличивается на 1. В рамках каждого этапа размер венгерского дерева увеличивается не более n раз. Очевидно, что за время <math>O(n^2) \;</math> можно обнаружить, какое ребро, ведущее из S в <math>\bar{T}</math>, первым войдет в подграф равенства (для этого нужно просто просмотреть все ребра). Общее время выполнения в таком случае составит <math>O(n^4) \;</math>. Теперь покажем, как реализовать это подход за время <math>O(n^3) \;</math>.