Нахождение наибольшего по весу вершинно-взвешенного паросочетания

Дан двудольный граф G. Для каждой вершины первой доли указан её вес. Требуется найти паросочетание наибольшего веса, т.е. с наибольшей суммой весов насыщенных вершин.

Ниже мы опишем и докажем алгоритм, основанный на алгоритме Куна, который будет находить оптимальное решение.

Алгоритм

Сам алгоритм чрезвычайно прост. Отсортируем вершины первой доли в порядке убывания (точнее говоря, невозрастания) весов, и применим к полученному графу алгоритм Куна.

Утверждается, что полученное при этом максимальное (с точки зрения количества рёбер) паросочетание будет и оптимальным с точки зрения суммы весов насыщенных вершин (несмотря на то, что после сортировки мы фактически больше не используем эти веса).

Таким образом, реализация будет примерно такой:

int n;
vector < vector<int> > g (n);
vector used (n);
vector<int> order (n); // список вершин, отсортированный по весу
... чтение ...

for (int i=0; i<n; ++i) {
	int v = order[i];
	used.assign (n, false);
	try_kuhn (v);
}

Функция try_kuhn() берётся безо всяких изменений из алгоритма Куна.

Доказательство

Напомним основные положения теории матроидов.

Матроид M - это упорядоченная пара (S,I), где S - некоторое множество, I - непустое семейство подмножеств множества S, которые удовлетворяют следующим условиям:

Множество S конечное.
Семейство I является наследственным, т.е. если какое-то множество принадлежит I, то все его подмножества также принадлежат I.
Структура M обладает свойством замены, т.е. если A∈I, и B∈I, и |A|<|B|, то найдётся такой элемент x∈A-B, что A∪x∈I.

Элементы семейства I называются независимыми подмножествами.

Матроид называется взвешенным, если для каждого элемента x∈S определён некоторый вес. Весом подмножества называется сумма весов его элементов.

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

отсортировать множество S по невозрастанию веса;
ans = [];
foreach (x in S)
	if (ans ∪ x ∈ I)
		ans = ans ∪ x;

Утверждается, что по окончании этого процесса мы получим подмножество с наибольшим весом.

Теперь докажем, что наша задача - не что иное, как взвешенный матроид.

Пусть S - множество всех вершин первой доли. Чтобы свести нашу задачу в двудольном графе к матроиду относительно вершин первой доли, поставим в соответствие каждому паросочетанию такое подмножество S, которое равно множеству насыщенных вершин первой доли. Можно также определить и обратное соответствие (из множества насыщенных вершин - в паросочетание), которое, хотя и не будет однозначным, однако вполне нас будет устраивать.

Тогда определим семейство I как семейство таких подмножеств множества S, для которых найдётся хотя бы одно соответствующее паросочетание.

Далее, для каждого элемента S, т.е. для каждой вершины первой доли, по условию определён некоторый вес. Причём вес подмножества, как нам и требуется в рамках теории матроидов, определяется как сумма весов элементов в нём.

Тогда задача о нахождении паросочетания наибольшего веса теперь переформулируется как задача нахождения независимого подмножества наибольшего веса.

Осталось проверить, что выполнены 3 вышеописанных условия, наложенных на матроид. Во-первых, очевидно, что S является конечным. Во-вторых, очевидно, что удаление ребра из паросочетания эквивалентно удалению вершины из множества насыщенных вершин, а потому свойство наследственности выполняется. В-третьих, как следует из корректности алгоритма Куна, если текущее паросочетание не максимально, то всегда найдётся такая вершина, которую можно будет насытить, не удаляя из множества насыщенных вершин другие вершины.

Итак, мы показали, что наша задача является взвешенным матроидом относительно множества насыщенных вершин первой доли, а потому к ней применим жадный алгоритм.

Осталось показать, что алгоритм Куна является этим жадным алгоритмом.

Однако это довольно очевидный факт. Алгоритм Куна на каждом шаге пытается насытить текущую вершину - либо просто проводя ребро в ненасыщенную вершину второй доли, либо находя удлиняющую цепь и чередуя паросочетание вдоль неё. И в том, и в другом случае никакие уже насыщенные вершины не перестают быть ненасыщенными, а ненасыщенные на предыдущих шагах вершины первой доли не насыщаются и на этом шаге. Таким образом, алгоритм Куна является жадным алгоритмом, строящим оптимальное независимое подмножества матроида, что и завершает наше доказательство.