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

Пусть дан [[полный граф|полный]] [[двудольный граф]] <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]. Будем предполагать, что всех веса ребер неотрицательны.

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

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

 

<math>\bar{S} = X \backslash S \;</math>.

 

Между S и <math>\bar{T}</math> не имеется ребер, поскольку в противном случае не было бы возможности полностью вырастить венгерские деревья. Поскольку венгерские деревья выращиваются в <math>G_{ \ell}\;</math>, альтернативные вершины в поиске помещаются в S и T. Для обновления меток следует взять метки из S и начать равномерно уменьшать их (скажем, на значение <math>\lambda \;</math>), в то же время увеличивая метки в T на то же значение <math>\lambda \;</math>. Этот подход гарантирует, что ребра, ведущие из S в T, не исчезнут из подграфа равенства (рис. 1).

Поскольку метки в 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>.

Рис. 1. Множества S и T, поддерживаемые алгоритмом

 

 

 

<math>slack(x, y) = \ell(x) + \ell(y) - w(x, y)</math>.

<math>slack[y] = min_{x \in S} \; slack(x, y)</math>.

Вычисление slack[y] для всех <math>y \in \bar{T} \;</math> требует <math>O(n^2) \;</math> времени в начале этапа. По мере продвижения по данному этапу все значения провисов легко обновляются за время O(n), поскольку все они изменяются на одну и ту же величину (метки вершин из S уменьшаются равномерным образом). При перемещении вершины u из <math>\bar{S}</math> в S необходимо перевычислить провисы вершин в <math>\bar{T}</math>, что требует O(n) времени. Однако перемещать вершину из <math>\bar{S}</math> в S можно не более n раз.

Таким образом, каждый этап может быть реализован за время <math>O(n^2) \;</math>. Поскольку имеется n этапов, общее время выполнения составиет <math>O(n^3) \;</math>. Для разреженных графов есть способ реализации алгоритма с временем выполнения O(n(m + n log n)) с использованием потоков минимальной стоимости [1], где m – количество ребер.