unique한 bipartite matching의 성질
한 쌍의 정점을 잇는 간선은 최대 하나이고(no parallel edges),모든 정점을 포함하는 매칭이 존재하는 이분그래프 G=(L, R, E)가 있다고 하자."이 그래프의 최대 매칭이 유일하다면 degree가 1인 정점이 항상 존재한다."에 대해 참/거짓을 밝히고자 한다. 모든 정점을 포함하는 매칭이 존재하므로 모든 정점의 degree는 1 이상이다.G=(L,R,E)의 모든 정점이 degree가 2 이상이라고 하자.여기서 서로 다른 매칭이 두 개 이상 존재한다는 것을 보이자. alternating path와 비슷한, 'alternating cycle'을 생각하자.alternating cycle이란, 그 간선들이 '매칭된 간선'과 '매칭되지 않은 간선'을 번갈아가는 사이클이다.예)1-2 x 3-4이런 ..
2015. 7. 5. 01:53