이번에 풀어볼 그래프이론(Grpah Theory)문제는 “Exhibit a maximum matching in the graph below, and use various results that we learned so far to give a short proof that it is a maximum matching.” 이다.
그래프이론(Grpah Theory)문제풀이
Exhibit a maximum matching in the graph below, and use various results that we learned so far to give a short proof that it is a maximum matching.
일단 문제에나온 그림은 아래와 같다.
풀이)
아래 그림의 (a)처럼 matching을 잡았다. augmenting M-path 를 찾으려 하지만 (b)에서 보듯이 찾을 수 없었다. 따라서 M은 maximum matching이다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제