아이고리즘

이전 글에서 Kőnig's Theorem, 쾨니그 정리를 증명했다. 핵심 아이디어만 말하자면 bipartite graph에서 모든 maximum matching에 등장하는 vertex가 하나 이상 존재함이었다. https://cultivated-algorist.tistory.com/entry/Kőnigs-theorem-쾨니그의-정리-증명 Kőnig's theorem (쾨니그의 정리) 증명 Kőnig's theorem. $G$가 bipartite라면 $G$의 maximum matching과 minimum node cover는 크기가 같다. 많은 증명들이 있지만 그 중에서 개인적으로 좋아하면서 (추측건데) 많이 보지 못했을 증명을 소개하고자 한.. cultivated-algorist.tistory.com 해..

Graph/Matching 2022. 7. 6. 12:54

Kőnig's theorem. $G$가 bipartite라면 $G$의 maximum matching과 minimum node cover는 크기가 같다. 많은 증명들이 있지만 그 중에서 개인적으로 좋아하면서 (추측건데) 많이 보지 못했을 증명을 소개하고자 한다. Matching과 Node cover의 정의. $G(V,E)$가 주어졌을 때 matching은 $E$의 부분집합이고 node cover는 $V$의 부분집합이다. 어떤 조건을 만족해야 하냐면 matching $M$은 $V$에서 어떤 node를 고르더라도 $M$에 incident한 edge가 최대 하나여야 하고 node cover $C$는 $E$에서 어떤 edge를 고르더라도 $C$에 그것의 두 endpoint중 최소 하나가 포함되어야 한다. (쉽게 ..

Graph/Matching 2022. 3. 25. 19:54