Bipartite_Matching (2) 썸네일형 리스트형 최소 경로 덮개 (Minimum Path Cover) 얼마 전 친한 형님이 또 재미있는 문제를 하나 소개해주었습니다. 처음에 전 그 문제가 NP-난해일 것이라고 생각했지만, 토의를 거친 끝에 그 문제가 순환이 없는 방향 그래프(directed acyclic graph, DAG)에서 최소 경로 덮개(minimum path cover)를 찾는 문제로 환원될 수 있다는 것을 찾아냈습니다. 또한 놀랍게도, 일반적인 그래프에서 최소 경로 덮개를 찾는 문제는 NP-난해하지만, DAG에서는 다항 시간에 찾을 수 있다는 것도 알게 되었습니다. Bipartite matching을 활용하면 된다는데, 곰곰이 생각해 보니 쉽게 보일 수 있더군요. 이번 포스트에서는 이에 대해서 간단히 알아보도록 하겠습니다. 문제를 엄밀히 정의하도록 하겠습니다. 입력으로는 방향이 있는 그래프(d.. 홀의 정리 (Hall's Theorem) 여러분이 어떤 단체의 인사 담당자라고 하죠. 총 다섯 명의 직원이 새로이 자리를 배치 받아야 하는 상황입니다. 고맙게도 충원되어야 하는 자리도 총 다섯 개입니다. 자애로운 여러분은 모든 직원들이 만족하도록 자리를 배치하고 싶어서 직원들에게 자신이 배치 받아도 좋은 자리가 어딘지를 먼저 물어 보았습니다. 직원은 알파벳(A-E)으로, 자리는 숫자(1-5)로 표현했을 때, 여러분은 직원들이 원하는 자리를 다음과 같이 표현하였습니다.이제 여러분은 직원들에게 자리를 배치해야 합니다. 아마도 여러분은 다음 그림과 같이 손쉽게 네 명은 배치할 수 있을 것입니다. 실제로 배치된 것을 빨간 실선으로 표현하였습니다.하지만 직원 E를 배치하지 못한 상황입니다. 과연 여러분은 모든 직원에게 서로 다른 자리를 하나씩 배치할 수.. 이전 1 다음
