이분매칭1 이분 매칭 (Bipartite graph) 이분 매칭에 앞서 이분 그래프의 정의부터 알아보자. 이분 그래프란 아래 조건을 만족하는 그래프이다. 노드를 두 그룹으로 나누는데 각 그룹이 간선을 공유하지 않는 그래프 예를 들면 이런 그래프가 있다. 이분 매칭 이분 매칭이란 이분 그래프에서 서로 다른 그룹에 속한 노드를 매칭 할 때, 최대한 많이 매칭 하는 것을 말한다. 이때 하나의 노드는 최대 하나의 간선만 가지도록 구성되어야 한다. 예제 그래프를 가지고 이분 매칭을 하는 방법을 하나씩 살펴보자. 예제 1. 초기 그래프 2. 첫번째 매칭 위 그래프에서 이분 매칭을 하기 위해 먼저 빨간 노드를 차례대로 순회하면서 파란 노드랑 연결시켜주는 작업을 시작한다. 2-1. 첫번째 매칭 후처리 첫 번째 빨간 노드에서 그래프를 순회하다가 매칭 할 수 있는 파란 노드.. 2019. 10. 17. 이전 1 다음
