Как уменьшить максимальный кардинальность двухстороннего соответствия для минимального покрытия пути?

Question

Я прочитал эти два вопроса: ссылка1 ссылка2

а также эта википедия

но я не могу понять, как решение проблемы максимального соответствия может быть использовано для решения минимального покрытия пути. Я знаю, что решение - это nm, где n - это число вершин в G, а m - максимальное совпадение, но я не могу найти причину.

Answer 1

Вот интуитивное объяснение этого факта (это не строгое доказательство): Давайте рассмотрим каждый путь в покрытии пути. Каждая вершина, кроме первой в пути, имеет уникального предшественника. Более того, каждая вершина имеет ровно одного преемника (кроме последнего на каждом пути). Вот почему мы можем сказать, что каждая вершина соответствует своему предшественнику. Если вершина ни к чему не соответствует, это первая вершина в некотором пути. Вот почему количество путей равно количеству несопоставленных вершин (каждый путь имеет ровно одну первую вершину). Число несопоставленных вершин, очевидно, равно общему количеству вершин минус количество совпадающих вершин. Вот так мы получаем n - m формула. Невозможно получить меньше путей, чем размер максимального соответствия (в противном случае n - m1 < n - m => m1 > m => m не максимум). В то же время мы можем построить решение с n - m пути явно.

Answer 2

• У вас есть n узлов слева & m узлов справа.
• После сопоставления вы вычисляете maxFlow f - максимальное количество совпадений.
• f узлы слева & f узлы справа уже находятся в минимальном ребре.
• Слева есть nf узлов, которые не совпадают, справа - mf таких узлов.
• Эти узлы еще не находятся в минимальном покрытии, потому что максимальное совпадение не включает их.
• Каждый из этих узлов может быть подключен к минимальному краю крышки. Таким образом, он добавляет (nf)+(mf) ребер.
• Таким образом, общее минимальное покрытие составляет f+(nf)+(mf)=n+mf

Вот небольшая проблема: https://code.google.com/codejam/contest/11254486/dashboard