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

Пусть дан [[полный граф|полный]] [[двудольный граф]] <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>\ell \;</math> как отображение множества вершин G на множество вещественных чисел, где <math>\ell(x) + \ell(y) \ge 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 исследуются все ребра, инцидентные этой вершине).''

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

 

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

 

<math>\bar{T} = Y \backslash T \;</math>.

 

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