4551
правка
Задача присваивания: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Паросочетание на взвешенных двудольных графах == Постанов…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 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\. | |||