한양과학기술고등학교

이분 그래프와 최대 매칭이란?개념

정점 집합을 두 그룹으로 나눴을 때, 같은 그룹 안에서는 절대 간선이 없고 서로 다른 그룹 사이에만 간선이 있는 그래프를 이분 그래프(Bipartite Graph)라고 한다. 학생 ↔ 동아리, 구직자 ↔ 일자리, 손님 ↔ 테이블처럼 "두 종류를 서로 연결"하는 문제는 대부분 이 형태다.

• 매칭(Matching) — 간선들의 부분집합인데, 어떤 정점도 두 번 이상 선택되지 않도록 고른 것.
• 최대 매칭(Maximum Matching) — 매칭에 포함된 간선 수가 가장 많은 매칭.
• 증대 경로(Augmenting Path) — 매칭 안 된 정점에서 시작해 매칭 간선과 비매칭 간선을 번갈아 타고 다시 매칭 안 된 정점에서 끝나는 경로. 이 경로를 찾아 선택을 뒤집으면 매칭 수가 1 늘어난다.

Kuhn's Algorithm — 학생을 하나씩 배정하며 자리를 양보시키기알고리즘

왼쪽 정점(학생)을 한 명씩 순서대로 처리한다. 그 학생이 갈 수 있는 동아리를 순서대로 확인하다가 빈 동아리를 만나면 바로 배정한다. 이미 다른 학생이 있는 동아리라면, 그 학생이 다른 동아리로 옮길 수 있는지 재귀적으로 확인한다 — 옮길 수 있다면 자리를 비켜주고 지금 학생이 그 자리를 차지한다. 이렇게 "자리 양보"가 연쇄적으로 일어나는 것이 바로 증대 경로를 실제로 뒤집는 과정이다.

인터랙티브 데모 — 5명의 학생, 4개의 동아리실습

Python 코드 — 재귀로 구현한 증대 경로 탐색코드

def try_kuhn(u, visited):
    # u(왼쪽 정점)가 갈 수 있는 동아리를 순서대로 확인
    for v in adj[u]:
        if v in visited:
            continue
        visited.add(v)
        # v가 비었거나, v를 차지한 학생이 다른 곳으로 옮길 수 있다면
        if v not in match_r or try_kuhn(match_r[v], visited):
            match_r[v] = u
            return True
    return False

match_r = {}                      # 동아리 -> 학생
for u in students:
    try_kuhn(u, visited=set())

max_matching = len(match_r)