Как конвертировать SPOJ Quest4 в Minimum Vertex Cover

Question

Ниже приведена проблема соответствия максимального двудольного: http://www.spoj.com/problems/QUEST4/ Через форумы я узнал, что эту проблему можно превратить в проблему минимального покрытия вершин, которая, в свою очередь, может быть решена с помощью Максимума Двухстороннее соответствие. Тем не менее, я не понимаю, как проблема была преобразована в Minimum Vertex Cover. Пожалуйста, помогите мне понять это.

Answer 1

Пусть C, R будет множеством всех строк и всех столбцов. Пусть теперь G - двудольный граф, имеющий ребра между C и R, где есть ребро (i,j) от C до R, если в i-й строке и j-м столбце есть отверстие.

Теперь рассмотрим покрытие вершин этого графа. Покрытие вершины графа является минимальным набором узлов, таким образом, что все ребра покрыты (каждое ребро падает по крайней мере на одну вершину в покрытии вершины).

В нашем графе задач каждое ребро представляет собой отверстие. Вершины представляют строки или столбцы. Цель - минимизировать блоки, закрывая все отверстия
что эквивалентно -
минимизируйте вершины, покрывая все ребра.