Максимальный двудольный граф (1, n) «соответствие»

Question

У меня есть двудольный граф. Я ищу максимальное (1, n) «соответствие», что означает, что каждая вершина из разбиения A имеет n связанных вершин из разбиения B.

На следующем рисунке показано максимальное (1,3) совпадение на графике. Края, выбранные для сопоставления, имеют красный цвет, а невыбранные края - черный.

См. Рисунок http://www.freeimagehosting.net/uploads/9a8df2d97c.gif

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

Если совпадающая мощность (n) не является обязательной, но является верхней границей (вершины из A могут иметь 0

Answer 1

Это NP-сложный, сокращение от задачи максимального независимого набора. Для любого графа G вы можете построить (за полиномиальное время) экземпляр вашей проблемы так, чтобы:

• Вершины в A представляют вершины G
• Каждая вершина из A связана ровно с n вершинами из B
• Любые две вершины из A имеют общего соседа в B, если и только если они связаны в G. Чтобы это было всегда возможно, выберите n = Δ (G).

Теперь максимальное «соответствие» в экземпляре возвращается к максимальному независимому набору в G.