[그래프] 이분 그래프(Bipartite Graph)와 이분 매칭(Bipartite Matching) with 쾨닉의 정리(Kőnig’s theorem)

이분 그래프란?

이분 그래프란 그래프의 모든 정점을 두 그룹으로 나누어 같은 그룹끼리 이어지는 간선이 없도록 만들 수 있는 그래프를 의미한다.

이렇게 되면 이분 그래프의 모든 간선은 서로 다른 그룹의 정점을 연결하게 된다.

 

이분 그래프의 예시(출처: 위키백과)

 

이분 그래프 판별

어떤 그래프가 이분 그래프인지 아닌지는 DFS나 BFS를 이용해 판별할 수 있다.

 

1. 특정 정점 하나를 잡아 A그룹으로 둔다.
2. 해당 정점과 이어진 정점들은 B그룹으로 둔다.
   마찬가지로 B그룹 정점과 이어진 정점들은 다시 A그룹으로 둔다.
3. 진행 중 모순이 발생했다면 해당 그래프는 이분 그래프가 아니다.

 

아래 문제를 한 번 풀어보자.

import sys
from collections import deque
input = sys.stdin.readline

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v)]
    types = [None] * v
    
    for _ in range(e):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        graph[a].append(b)
        graph[b].append(a)
    
    no = False
    q = deque()
    
    for i in range(v):
        if types[i] != None: continue
        types[i] = True
        q.append(i)
        while q:
            now = q.popleft()
            for next in graph[now]:
                if types[next] == types[now]:
                    no = True
                    break
                elif types[next] == None:
                    types[next] = not types[now]
                    q.append(next)
            if no: break
        if no: break
    
    print("NO" if no else "YES")

1707번: 이분 그래프

 

이분 매칭이란?

이분 매칭이란 이분 그래프에서 각 정점들이 최대 하나의 간선만 가지도록 구성한 것이다.

조금 쉽게 말하면, 그룹 A의 정점과 그룹 B의 정점을 말 그대로 매칭시키는 것을 의미한다.

 

대부분의 문제에서는 그래프에서 만들 수 있는 최대 이분 매칭의 수를 구해야 한다.

만약 최대 유량(네트워크 플로우) 문제에 대해 알고 있다면, A에서 B 방향으로 연결되어 있거 모든 간선의 가중치가 1인 최대 유량 문제라고 생각하면 쉽다.

아래에서 소개하고자 하는 최대 이분 매칭 알고리즘도 최대 유량 문제의 포드-풀커슨 알고리즘을 변형한 느낌이다.

 

이분 매칭 구해보기

이분 그래프에서의 최대 매칭 수는 DFS를 이용해 $O(VE)$만에 구할 수 있다.

 

1. 첫 정점은 바로 첫 간선을 따라 매칭시킨다.
2. 다음 정점도 첫 간선을 따라 매칭시킨다.
   만약 도착한 정점이 이미 선택되었다면, 이전 정점으로 돌아가 해당 정점은 두번째 간선을 따라 매칭한다.
3. 위 방식으로 계속 매칭시키거나 안되면 돌아가는 작업을 반복한다.

 

구현해보기 (Python)

백준 11375번의 정답 코드이기도 하다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
works = [list(map(int, input().split()))[1:] for _ in range(n)]
assign = [-1] * (m + 1)
visited = [False] * (m + 1)

def dfs(target):
    for work in works[target]:
        if visited[work] :
            continue
        visited[work] = True
        
        if assign[work] < 0 or dfs(assign[work]):
            assign[work] = target
            return 1
    
    return 0

def run(target):
    global visited
    visited = [False] * (m + 1)
    return dfs(target)

print(sum([run(i) for i in range(n)]))

 

위 코드에서의 visited는 사람이 아닌 일을 기준으로 작성하였는데, 그냥 사람을 기준으로 작성해도 된다.

그 경우에는 visited인지 체크하는 부분과 True로 바꾸는 부분이 for문 밖으로 나와야 한다는 점만 주의해주자.

 

추가로 몇 가지 주의할 점이 있다.

• 모든 정점에 대해 매칭을 시도해야 하므로 매칭을 $V$번 진행해야 한다. (마지막 줄 참고)
• 매 진행시마다 visited는 초기화해야하나, assign은 건드리면 안된다. (run 함수 참고)

 

쾨닉의 정리(Kőnig’s theorem)

쾨닉의 정리는 이분 그래프에서 최대 매칭 문제와 최소 버텍스 커버 문제가 동치라는 정리이다.

최소 버텍스 커버(Minimum Vertex Cover) 문제는 모든 간선의 최소한 한 끝 점이 선택된 정점과 연결되어 있도록 정점을 뽑을 때, 뽑아야 하는 정점의 최소 개수를 의미한다.

최대 이분 매칭 수와 최소 버텍스 커버 수가 동일하다는 것만 알아두자.

 

관련 문제 (BOJ)

• [17209] 새내기와 헌내기: 이분 그래프 판별 응용 문제
• [2188] 축사 배정: 이분 매칭을 그대로 쓰면 되는 문제
• [1017] 소수 쌍: 이분 매칭 + 소수 판별
• [1867] 돌멩이 제거: 쾨닉의 정리 응용