Hall's Theorem, Kőnig's Theorem. 하나로 다른 하나 증명하기
이전 글에서 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
