noeffserv   10달 전

이 문제 풀긴 풀었는데.. 이해가 안가네요 ㅠ

미니멈 버텍스 커버 문제 인건 납득이 가는데

해법이 왜 맥시멈 매칭인지 모르겠습니다. 도와주세요ㅠ

koosaga   10달 전

1. 그래프가 격자 모양의 그래프이며 체스판을 생각해보면 이러한 형태의 그래프가 이분 그래프임을 알 수 있습니다.

2. 쾨닉의 정리에 의해서 https://en.wikipedia.org/wiki/K%C5%91nig's_theorem... 이분 그래프에서 minimum vertex cover의 크기는 maximum matching의 크기와 같습니다.

noeffserv   10달 전

빠른 답변 감사합니다.

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