Задача присваивания

Ключевые слова и синонимы

Паросочетание на взвешенных двудольных графах

Постановка задачи

Пусть дан полный двудольный граф G = (X, F, Ix, Y) с присвоенным каждому ребру (x, y) весом w(x, y). Паросочетание M представляет собой подмножество ребер, такое, что никакие два ребра в M не имеют общей вершины. Паросочетание является совершенным, если в него входят все вершины. Предположим, что |X| = |Y| = n. Задача поиска паросочетания на взвешенных двудольных графах заключается в нахождении паросочетания с максимальным общим весом, где w(M) = Pe2M w(e). Поскольку граф G является полным и двудольным, у него имеется совершенное паросочетание. Алгоритм для решения данной задачи предложили Кун [4] и Манкрес [6]. Будем предполагать, что всех веса ребер неотрицательны.

Основные результаты

Определим допустимую разметку вершин £ как отображение множества вершин G на множество вещественных чисел, где £(x) + £(y) > w(x;y):

Назовем l(x) меткой вершины x. Допустимую разметку вершин легко вычислить следующим образом: 8y 2 Y l(y) = 0 and 8x 2 X £(x) = maxw(x; y): y2Y

Определим подграф равенства, G^, как остовный подграф G, содержащий все вершины G и только те ребра (x, y), веса которых удовлетворяют условию w(x, y) =

Связь между подграфами равенства и паросочетаниями с максимальным весом задается следующей теоремой.

Теорема 1. Если подграф равенства Gi содержит совершенное паросочетание M*, то M* является в G паросочетанием с максимальным весом.

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

Высокоуровневое описание

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

Пусть S – дерево свободных вершин в X. Вырастим венгерские деревья из каждой вершины S. Пусть T – вершины из Y, встретившиеся в поиске дополняющего пути из вершин в S. Добавим все вершины из X, встретившиеся в поиске, в S.

Стоит отметить свойство данного алгоритма: ~s = XnS: T =YnT : \S\>\T\.