이분매칭

[1. 개요]

이분 매칭을 설명하기에 앞서 이분 그래프에 대한 개념 정의

• 그래프의 모든 정점이 두 그룹으로 나누어 질 때
• 서로 다른 그룹의 정점들은 연결되지만
• 같은 그룹의 정점들은 서로 연결하지 않는 형태의 그래프
• 두 집합 간의 대응 관계를 표현하기 위해 사용
• https://testkernelv2.tistory.com/338

매칭

• 그래프에서 끝점을 공유하지 않는 간선의 집합을 의미한다.

여기서 끝점을 공유하지 않는다는 의미는 아래와 같다.

• 두개 이상의 간선이 공유하는 정점이 있는 경우.

아래와 같은 형태의 그래프에서

어떤 조건을 만족하는 edge 만 선별하였다고 가정했을 때,

• 빨간색 간선이 선별된 edge

매칭인 경우,  edge 간 공유하는 정점이 없다.

매칭이 아닌 경우, edge 간 공유하는 정점이 있다.

 

그래서 매칭 문제(최대 매칭 문제) 는 그래프에서 가장 큰 매칭을 찾는 문제를 말하며,

• 가장 큰 매칭이 의미하는 바는 가장 많이 매칭 시키는 것
• 전체 그래프에서 공유하는 정점이 없이 조건에 맞는 edge 를 최대로 선별 하는 것.  

 이분 매칭은 이분 그래프에서 최대 매칭을 찾는 것이다.

• 모든 유형의 그래프에서 찾는 방식
  # cf) Edomond`s matching algorithm

---

[2. 이분 매칭의 중요성]

이분 그래프는 현실 세계에서 직관적인 의미를 갖는다.

• 사람과 각 사람이 할 수 있는 작업 목록이 있을 때 작업을 어떻게 분배할 지..
• 사람 그룹과 작업 그룹이 이분 그래프를 형성하기 때문에, 이분 그래프 형성..

---

[3. 네트워크 유량을 이용한 해결]

해결 전략

1. Source -> Group A ---> Group B -> Sink 형태로 그래프를 구축한다.
2. 모든 간선의 용량은 1로 설정한다.
3. 최대 유량을 구한 뒤, 유량이 흐르는 간선들을 모은다.
   # edge 의 한쪽 정점이 Source 혹은 Sink 인 edge 는 제거해야 함(?)

시간 복잡도

• 위와 같은 경우 네트워크의 최대 유량은 O(|V|) 이다.
• 포드-풀커슨 알고리즘은 최대 유량에 비례하므로
• O(|V||E|) 가 된다.

---

[4. 이분 그래프 형태를 이용한 해결]

포드-풀커슨 알고리즘을 dfs 로 구현할 경우 문제점

• 수행시간이 총 유량에 비례한다.

하지만, 이분 매칭처럼 최대 유량이 제한되어 있는 경우에는 큰 상관이 없다.

• 최대로 커질 수 있는게 정점의 개수만큼이다.
• stack 을 따라가면 되므로, 증가 경로를 직접 찾을 필요가 없다.
• 모든 증가 경로의 용량이 1이다. (모든 간선의 용량이 1이므로)

그 밖의 특징

• 탐색 도중, 반대편 그룹(GroupA, GroupB) 에 속한 정점에 도달했을 때,
• 이 정점이 이미 매칭 된 상태라면, 증가 경로의 다음 간선은 유일하게 결정 된다. (?)
  # GroupB 를 기준으로 생각해보면, 이 그룹에 속한 정점에서 나가는 edge 는 sink 로 가는 edge 가 유일
  # 이 edge 가 이미 매칭된 상황이면, 이 간선에 잔여 용량은 없다.
  # 이 때는, 알고리즘 특성 상 흘러 들어오는 유량을 상쇄하려는데,
  # 현재 정점으로 유량을 보내주는 정점은 현재 정점과 매칭 된 점 뿐이다 (?).
• source, sink 가 따로 필요하지 않다.

---

[5. 코드]

---

[6. 코드 부가 설명]

dfs 함수에서 헷갈렸던 부분에 대한 정리

1. 매칭이 안된 경우, 바로 매칭 하고 true 반환 하여 종료 하는 건 => OK
2. 이미 매칭이 된 경우, group b 가 매칭 된 점(group A 에 속한) 에서 부터 dfs 를 하는 이유
3. 방문 배열을 group A 에 대해서만 초기화 하는 이유

먼저, 이미 u 와  매칭 된 v 에 대해서, u 부터 dfs 를 다시하는 이유

• 아래와 같은 상황에서 정점 방문 순서 상 1-3 정점이 서로 매칭 됨
• 이 후, group A 에 속한 2번 정점을 매칭해야 하는데, 3번 정점은 이미 group A 에 속한 1번 정점과 매칭 되어 있음.
• 그러나, 1번 정점은 4번 정점과도 매칭 될 수 있음.
  => 바로 이 부분을 확인 하기 위해  2번 단계를 수행하는 것이다.
• 결국, group A 에 속한 정점이 기준이 되어 dfs를 수행하며, group B 에 속한 정점은 매칭여부를 통해 방문 여부를 확인 할 수 있다.
  => 3번에 대한 이유

최초,

순서 상, 1-3 이 먼저 매칭

2번 정점의 매칭 확인 시점

최종 결과