그래프 (10) - 이분 매칭(최소 버텍스 커버, 최대 독립 집합)

 

 

이분 그래프(bipartite graph)란 정점을 두 그룹($A, B$)로 나눴을 때, $A$와 $B$ 간에만 간선이 존재하고 그룹 내부에는 간선이 존재하지 않도록 만들 수 있는 그래프를 의미한다. 어떤 그래프가 이분 그래프인지 판별하는 방법은 간단하다. 탐색을 수행하면서 정점을 빨강/파랑으로 색칠해 주는데, 빨강색 정점에 인접한 정점은 모두 파란색으로 색칠되어야 하며, 파랑색 정점에 인접한 정점은 모두 빨간색으로 색칠되어야 한다. 그렇지 않으면 이분 그래프라고 볼 수 없다.

 

이분 매칭(bipartite matching)은 이분 그래프에서 최대 매칭을 찾는 알고리즘이다. 매칭(matching)은 정점을 공유하지 않도록 간선을 선택하는 방법이다. 정점의 입장에서는 최대 하나의 다른 정점과 연결되도록 하는 방법이라고 생각할 수도 있겠다. 일반적인 그래프에서 최대 매칭을 찾는 것은 보다 복잡하지만, 이분 그래프에서 최대 매칭을 찾는 방법은 전편에 다루었던 유량의 개념을 도입해 쉽게 찾을 수 있다.

 

 

이분 매칭

정점 그룹 $A$와 $B$를 매칭시키는 문제는, $S \to A \to B \to T$의 방향으로 용량이 정의된 그래프의 최대 유량을 찾는 문제로 변형할 수 있다. 이때 $S \to A$, $B \to T$의 모든 간선은 용량이 1이며, $A \to B$의 모든 간선은 용량이 $\infty$이다. 에드몬드-카프 알고리즘에 따라 가능한 경로를 하나 찾아 1의 유량을 흘리는 것을 반복한다. 반대로 -1의 유량을 흘림으로써 증가 경로가 있을 때에는 기존의 경로를 취소할 수 있도록 한다.

 

다만 이분 매칭의 실제 구현에 있어서는, 그래프의 형태가 단순하고 이미 정해져 있으므로 일반적인 최대 유량 문제에 비해 보다 간결하게 구현할 수 있다. 하나의 증가 경로를 찾을 때 $A$의 특정 정점을 방문했는지 여부를 나타내는 $visited$ 배열, $A$와 $B$ 간 매칭 결과를 담는 배열 $atob$, $btoa$를 정의하자.

1. 아직 매칭되지 않은 정점 $u \in A$를 찾고, $visited$를 초기화한다.
2. $u$와 인접한 정점 $v \in B$들을 살펴본다. $v$가 아직 매칭되지 않았다면 $u$와 매칭시킨다. $v$가 매칭되었더라도, $btoa[v]$를 아직 방문하지 않았다면 해당 정점으로 dfs한다(음의 유량을 흘림으로써 증가 경로를 찾는 것과 비슷하다).
3. 2에서 매칭이 성공하면 $atob[u]=v, btoa[v]=u$로 한다.

atob = [-1]*(N+1)
btoa = [-1]*(M+1)
def dfs(u):
    visited[u] = True
    for v in graph[u]:
        if btoa[v] == -1 or ((not visited[btoa[v]]) and dfs(btoa[v])):
            atob[u] = v
            btoa[v] = u
            return True
    return False

res = 0
for i in range(1, N+1):
    if atob[i] == -1:
        visited = [False]*(N+1)
        if dfs(i): res += 1

 

DFS를 최대 V번 수행하므로, 이분 매칭의 시간복잡도는 $O(VE)$가 된다.

 

 

 

최소 버텍스 커버

이분 매칭은 다양하게 응용될 수 있는데, 대표적으로 최소 버텍스 커버(minimum vertex cover)를 구하는 문제에 활용된다. 최소 버텍스 커버는 그래프의 모든 간선의 양 끝점 중 최소 하나를 포함하는 정점 집합을 최소로 만드는 문제이다. 

 

출처: 위키백과

 

일반적인 그래프에서 이 문제는 NP-hard에 속해 다항 시간 안에 풀 수 없다. 그러나 이분 그래프에서는 쾨니그의 정리(Kőnig's Theorem)에 의해 최대 매칭의 크기와 최소 버텍스 커버의 크기가 동일함이 알려져 있다. 최소 버텍스 커버를 구하는 방법은 아래와 같다.

 

1. 매칭되지 않은 정점 $u \in A$에서부터 시작한다.
2. $u$에서 매칭되지 않은 간선을 통해 도달 가능한 $v \in B$를 찾고, $v$와 매칭된 정점 $btoa[v]$로 dfs한다.
3. 탐색한 정점들의 집합 $X$에 대해, $M = (A-X) \cup (B\cap  X)$가 최소 버텍스 커버가 된다.

 

즉, A의 매칭되지 않은 정점 각각에서부터 시작해, '매칭되지 않은 간선 → 매칭된 간선 → 매칭되지 않은 간선 → ...'을 번갈아 선택하는 경로(이를 '교대 경로'라 한다)로 도달 가능한 정점들의 집합 $X$를 구하는 식이다. 알고리즘의 증명은 다음과 같다.

 

• 그래프의 임의의 간선 $(u,v)$에 대해 $u$나 $v$ 중 하나는 $M$에 속해야 한다.
• 만약 $u \in A-X$라면 이는 자명하다. 만약 $u \in X$라면, $v \in X$여야 한다. $(u,v)$가 매칭된 간선이라면 $u$가 매칭된 정점이므로 $v$로부터 교대 경로를 통해 들어왔을 것이므로 $v \in X$이고, $(u,v)$가 매칭되지 않은 간선이라면 $u$는 교대 경로의 시작점이므로 $v \in X$이다.
• 한편, $A-X$와 $B \cap X$의 정점들은 모두 매칭되어 있으며, $M$는 임의의 매칭된 간선 $(u,v)$에서 하나의 정점만을 포함한다. 따라서 $M$의 크기는 최대 매칭의 크기와 동일하고, 쾨니그의 정리에 의해 '최소'임이 증명된다.

x_a = [False]*(N+1)
x_b = [False]*(M+1)

def mvc_dfs(u):
    x_a[u] = True
    for v in adj[u]:
        if v != atob[u] and not x_b[v]:
            x_b[v] = True
            mvc_dfs(btoa[v])

for i in range(1, N+1):
    if atob[i] == -1:
        mvc_dfs(i)

mvc = [i for i in range(1, N+1) if not x_a[i]] + [i for i in range(1, M+1) if x_b[i]]

 

 

 

최대 독립 집합

최대 독립 집합(maximum independent set)은 간선으로 서로 연결되어 있지 않은 정점 집합을 최대로 만드는 문제이다. 전체 정점 $V$에서 최소 버텍스 커버를 제외하여 구할 수 있음을 직관적으로 파악할 수 있다. 따라서 이분 그래프에서의 최대 독립 집합 문제 역시 이분 매칭으로 간단히 구할 수 있다.

 

유명한 문제로 컨닝 2(BOJ 11014)가 있다. 컨닝이 가능한 자리끼리 연결해 보면, 세로줄 단위로 보았을 때 세로줄 안에서는 간선이 연결되어 있지 않으며 바로 양 옆의 세로줄과만 연결되어 있다. 따라서 홀수 번째 세로줄 / 짝수 번째 세로줄을 각각 그룹 $A, B$라 보고 이분 매칭이 가능하다. 이분 매칭에서의 최대 독립 집합의 수를 구하여 풀 수 있다.