[그래프] Graph 13: maximum matching 이분 그래프에서 최대 매칭

1. 매칭 문제

 

N명을 둘씩 짝으로 묶으려고한다.

 

단 사이가 좋은 사람끼리만 짝을 지어준다고 할때

 

모든 학생에게 짝을 지어 줄 수 있는지, 불가능하다면 최대 몇 쌍이나 만들 수 있는지 계산하는 문제가

 

매칭 문제의 예시이다.

 

 

 

이런 문제들은 그래프로 간단하게 표현할 수 있다.

 

각 사람을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다.

 

이 때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다.

 

이런 간선의 집합을 이 그래프의 매칭(matching)이라고 한다.

 

이때 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(maximum matching), 매칭 문제라고 부른다.

 

 

매칭 문제는 직관적인 정의를 가진 중요한 문제이다.

 

하지만 모든 그래프에 대해 매칭 문제를 해결하는 일반적인 알고리즘은 꽤나 복잡하고 까다롭다.

 

프로그래밍 대회에서는 매칭의 좀더 단순한 형태가 등장한다.

 

이분 그래프에서 최대 매칭을 찾는 문제가 주로 나온다고 한다.

 

 

2. 이분 매칭의 중요성

 

모든 간선이 서로 다른 그룹의 정점들을 연결하도록 할 수 있는 그래프들을 이분 그래프라고 한다.

 

정점의 집합을 색으로 구분해보면, 모든 간선이 서로 다른 색의 정점을 연결하고 있는것을 볼 수 있다.

 

이분 그래프는 두 집합 간의 대응 관계를 표현하기 위해 흔히 사용된다.

 

가장 전형적인 예로 작업 배분을 들 수 있다.

 

모든 사람이 다 모든 작업을 할 수 있는 것은 아니라고 하자,

 

이와 같은 제약 조건을 이분 그래프로 쉽게 표현할 수 있다.

 

각 사람을 나타내는 정점과 작업을 나타내는 정점들을 갖는 그래프를 만든 뒤,

 

각 사람과 그 사람이 할 수 있는 작업을 간선으로 연결하면 된다.

 

이와 같은 이분 그래프에서 최대 매칭은 가능한 한 많은 작업과 사람을 짝지을 수 있는 방법을 나타낸다.

 

 

이렇게 이분 그래프는 현실 세계에서 직관적인 의미를 가지기 때문에 이분 그래프에 대한 매칭은 따로 언급할 가치가 있다.

 

 

 

 

3. 네트워크 유량으로 이분 매칭 풀기

 

네트워크 유량을 이용하면 이분 매칭을 아주 간단하게 풀 수 있다.

 

그룹을 나누어 위와 같이 소스와 싱크를 붙이면 된다.

 

이때 모든 간선의 용량을 1 로 하고 이 그래프의 최대 유량을 구한 뒤 유량이 흐르는 간선들을 모으면 최대 매칭이 됨을 알 수 있다.

 

이 경우 네트워크의 최대 유량이 O(|V|)이므로 bfs는 최대 O(|V|)번만 하게 된다. 따라서 시간 복잡도는 O(|E||V|)가 된다.

 

 

 

 

4. 이분 매칭 구현하기

 

포드-풀커슨 알고리즘을 응용해서 이분 매칭을 구현할 수도 있지만,

 

이분 매칭 문제는 일반적인 네트워크 유량 문제보다 비교적 자주 출현하기 때문에 

 

좀더 단순한 형태의 코드를 작성하는게 편리하다.

 

이분 매칭의 속성을 이용하면 단순한 알고리즘을 구현할 수 있다.

 

이 구현은 포드-풀커슨 알고리즘처럼 증가 경로를 찾은 뒤 유량을 보내는 것을 반복한다

 

 

const int MAX_N = 100, MAX_M = 100;
int n, m;
 
bool adj[MAX_N][MAX_M];
 
vector<int> aMatch, bMatch;
vector<bool> visited;
 
bool dfs(int a)
{
    if(visited[a]) return false;
    visited[a] = true;
    for(int b = 0; b < m; b++)
        if(adj[a][b])
            if(bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
                return true;
            }
    return false;
}
 
int bipartiteMatch()
{
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
    int size = 0;
    for(int start = 0; start < n; start++)
    {
        visited = vector<bool>(n, false);
        if(dfs(start))
            ++size;
    }
    return size;
}

- 알고리즘 문제해결전략 1036p

 

[그래프] TRAPCARD 함정 설치

[그래프] BISHOPS 비숍