조합론적 최적화 (22) 썸네일형 리스트형 쾨니그의 정리 (Kőnig's Theorem) 이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보다 많은 경우 다른 최적화 문제와 크게 관련이 있는 것을 볼 수 있습니다. 대표적인 예시가 바로 최대유량 최소컷 정리(maximum flow minimum cut theorem)입니다. 이 정리에 따르면, 어떤 flow network에서 유량(flow)을 최대화하는 문제는 곧 그 network의 최소 컷(cut)을 찾는 문제와 동일하다는 사실을 알 수 있습니다.. 이번에 함께 살펴 볼 문제들도 이와 비슷한 관계가 있습니다. 바로 matching과 vertex cover입니.. 홀의 정리 (Hall's Theorem) 여러분이 어떤 단체의 인사 담당자라고 하죠. 총 다섯 명의 직원이 새로이 자리를 배치 받아야 하는 상황입니다. 고맙게도 충원되어야 하는 자리도 총 다섯 개입니다. 자애로운 여러분은 모든 직원들이 만족하도록 자리를 배치하고 싶어서 직원들에게 자신이 배치 받아도 좋은 자리가 어딘지를 먼저 물어 보았습니다. 직원은 알파벳(A-E)으로, 자리는 숫자(1-5)로 표현했을 때, 여러분은 직원들이 원하는 자리를 다음과 같이 표현하였습니다.이제 여러분은 직원들에게 자리를 배치해야 합니다. 아마도 여러분은 다음 그림과 같이 손쉽게 네 명은 배치할 수 있을 것입니다. 실제로 배치된 것을 빨간 실선으로 표현하였습니다.하지만 직원 E를 배치하지 못한 상황입니다. 과연 여러분은 모든 직원에게 서로 다른 자리를 하나씩 배치할 수.. 이전 1 2 3 다음
