keh0711   5달 전

아래 질문을 읽어보고 궁금한 점이 있어 글을 적습니다.

게시판을 이분매칭 그래프로 아래와 같이 표현한다면
테이핑(1,2,3,4...) 막는 구멍(a,b,c,d,e...)로 하면
1->a
2->b,c
3->c,d
4->d
이것을 기본적인 이분매칭 소스로 해결한다면 1:1로 매칭되기 때문에 max matching은 4이 되는데...
이것이 minimum vertex cover의 수(여기서는 3이 정답)와 어떻게 일치하는지 궁금합니다.

제가 잘못 이해하고 있는 부분을 알려주시면 감사하겠습니다^^

댓글을 작성하려면 로그인해야 합니다.