counterexample (1) 썸네일형 리스트형 이분 매칭에 관한 몇 가지 반례들 매칭(matching), 특히 이분 매칭(bipartite matching)은 제 주된 연구 분야 중 하나입니다. 제 블로그에 매칭 관련된 포스트가 가장 많은 것을 보면 쉽게 유추할 수 있으시리라 생각합니다. 최근 개인적으로 이분 매칭과 관련하여 몇 가지 명제를 세워 증명해 보려고 했습니다. 만약 참으로 밝혀진다면 제가 요즘 하는 연구에 도움이 될 명제들이었습니다. 하지만 안타깝게도 모두 반례가 존재하였습니다. 어디 가서 써 먹을 곳도 없다 보니 약간은 울적한 마음에 블로그에라도 적어 보려고 합니다. 혹여 비슷한 주제를 고민하시는 분들이 계시다면 이 글이 약간의 도움이 되었으면 합니다. 차수와 간선 서로소인 최대 매칭의 개수 첫 번째 명제는 다음과 같았습니다. 어떤 이분 그래프의 최소 차수(degree).. 이전 1 다음
