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

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