그래프의 완전하지 않은 2 진 매칭을 어떻게 찾을 수 있습니까?

Question

즉, 일부 정점이 다른 정점에 연결되지 않을 수도있는 그래프의 2 부분 일치를 찾는 방법은 무엇입니까?

EDIT : 하나의 추가 조건으로 가장자리에도 가중치가 있다고 가정하고 총 가장자리 무게가 최소화되도록 (또는 최대화하여) 일치를 원합니다.

Answer 1

먼저, 가중치가 음수가 아닌 것으로 가정합니다. 편집 된 버전에서

, 당신은 assignment problem 대해 얘기 : N 에이전트는 각 에이전트가 각 작업에 대한 임의의 음이 아닌 비용이 경우 각각의 고유 한 작업을 수행하기 위해 할당. 이 설명은 완벽한 2 부분 일치를위한 것이지만 몇 가지 트릭을 수행 할 수 있습니다. 측면의 균형을 잡으려면 상대방의 모든 요소에 가중치가 0 인 정점을 추가하면 아무런 조치도 취하지 않은 것과 관련된 비용은 0이 아니라고 할 수 있습니다. 누락 된 링크는 모든 실제 비용의 합계를 초과하는 비용으로 모델링 할 수 있으므로 문제를 해결할 수없는 경우에만 선택됩니다. 수정 된 버전의 경우 Hungarian Algorithm을 사용합니다. 마지막으로,이 문제는 "최대 가중 두 부분 일치"라고도하며 알고리즘에 대한 다른 참조는 두 번째 단락 maximum matchings in bipartite graphs에서 찾을 수 있습니다.

편집 : 비용을 최소화하지 않고 최대화하려면 비용을 반납해야합니다. 최대 비용을 찾고 최대 비용에서 각 비용을 뺍니다. 그런 다음 누락 된 링크가있는 경우 비용 0 링크를 사용하지 않으려합니다.

Answer 2

Hopcroft-Karp algorithm을 사용하면 원하는대로 정확하게 수행 할 수 있습니다.