10. 매칭 알고리즘 (Matching Algorithm)
2020.10.18
매칭Matching이란, 어떤 그래프 $G=\{V, E\}$의 부 그래프 중, 모든 노드의 차수가 1인 그래프이다. 우리나라에서는 부합이라고 부르기도 한다. 예를들어, 위 그래프에서 $1, 4, 5, 2$를 뽑아내어 만든 부 그래프는 크기 2인 매칭이다. 그러나, $1,2, 4, 5,6$은 $1$이 2의 차수를 가지므로 매칭이 아니다. $G$가 $n$개의 노드를 가질 때, $n/2$의 크기의 매칭이 존재한다면 모든 노드가 매칭에 관여한 것이다. 이런 경우를 완벽 매칭perfect matching이라 한다. 매칭의 가중치 그래프의 간선에 가중치가 부여될 수 있다. 이때, 매칭의 가중치는 매칭에 포함된 간선들의 가중치의 합이다. 위 그래프에서, $m_1 = (1,3), (2,4)$ 혹은 $m_2 = (1,4..