최대 이분 매칭을 위한 Kuhn 알고리즘¶

문제¶

$n$개의 정점과 $m$개의 간선을 가진 이분 그래프 $G$가 주어집니다. 최대 매칭을 찾으십시오. 즉, 선택한 어떤 간선도 다른 선택한 간선과 정점을 공유하지 않도록 가능한 한 많은 간선을 선택하십시오.

알고리즘 설명¶

필요한 정의¶

매칭 $M$은 그래프에서 서로 인접하지 않은 간선들의 집합입니다(다시 말해, 그래프 $M$의 어떤 정점에도 이 집합의 간선이 두 개 이상 연결되어서는 안 됩니다). 매칭의 크기(cardinality)는 매칭에 포함된 간선의 개수입니다. 매칭에 속한 간선과 연결된 모든 정점(즉, $M$으로 이루어진 부분 그래프에서 차수가 정확히 1인 정점)을 이 매칭에 의해 포화(saturated)되었다고 합니다.
극대 매칭(maximal matching)은 그래프 $G$의 매칭 $M$ 중에서 다른 어떤 매칭의 부분집합도 아닌 매칭입니다.
최대 매칭(maximum matching, 최대 크기 매칭이라고도 합니다)은 가능한 한 가장 많은 간선을 포함하는 매칭입니다. 모든 최대 매칭은 극대 매칭입니다.
여기서 길이가 $k$인 경로는 별도로 명시하지 않는 한 $k$개의 간선을 포함하는 단순 경로(즉, 정점이나 간선이 반복되지 않는 경로)를 의미합니다.
교대 경로(alternating path)(이분 그래프에서 어떤 매칭에 대해 정의됩니다)는 간선들이 번갈아 가며 매칭에 속하고 / 속하지 않는 경로입니다.
증가 경로(augmenting path)(이분 그래프에서 어떤 매칭에 대해 정의됩니다)는 시작 정점과 끝 정점이 포화되지 않은, 즉 매칭에 속하지 않는 교대 경로입니다.
집합 $A$와 $B$의 대칭차집합(symmetric difference, 분리 합집합(disjunctive union)이라고도 합니다)은 $A \oplus B$로 나타내며, $A$와 $B$ 중 정확히 하나에만 속하고 둘 모두에는 속하지 않는 모든 원소의 집합입니다. 즉, $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$입니다.

Berge의 보조정리¶

이 보조정리는 1957년 프랑스의 수학자 Claude Berge가 증명하였지만, 이미 1891년 덴마크의 수학자 Julius Petersen과 1931년 헝가리의 수학자 Dénes Kőnig가 관찰한 바 있습니다.

명제¶

매칭 $M$이 최대 매칭입니다 $\Leftrightarrow$ 매칭 $M$에 대한 증가 경로가 존재하지 않습니다.

증명¶

양방향 함의의 두 방향을 모두 귀류법으로 증명하겠습니다.

매칭 $M$이 최대 매칭입니다 $\Rightarrow$ 매칭 $M$에 대한 증가 경로가 존재하지 않습니다.

주어진 최대 매칭 $M$에 대한 증가 경로 $P$가 존재한다고 가정합시다. 이 증가 경로 $P$는 반드시 홀수 길이를 가지며, $M$에 속하지 않는 간선이 $M$에 속하는 간선보다 하나 더 많습니다. 원래 매칭 $M$의 간선 중 $P$에도 속하는 간선을 제외한 모든 간선과, $P$의 간선 중 $M$에 속하지 않는 간선을 포함하여 새로운 매칭 $M'$을 만듭니다. $P$의 시작 정점과 끝 정점은 $M$에 의해 포화되지 않았고, 나머지 정점들은 매칭 $P \cap M$에 의해서만 포화되므로 이는 올바른 매칭입니다. 이 새로운 매칭 $M'$은 $M$보다 간선이 하나 더 많으므로, $M$은 최대 매칭일 수 없습니다.

형식적으로, 어떤 최대 매칭 $M$에 대한 증가 경로 $P$가 주어지면 매칭 $M' = P \oplus M$은 $|M'| = |M| + 1$을 만족하므로 모순입니다.
매칭 $M$이 최대 매칭입니다 $\Leftarrow$ 매칭 $M$에 대한 증가 경로가 존재하지 않습니다.

$M$보다 크기가 더 큰 매칭 $M'$이 존재한다고 합시다. 대칭차 $Q = M \oplus M'$을 생각해 봅시다. 부분 그래프 $Q$는 더 이상 반드시 매칭이라고 할 수 없습니다. $Q$의 모든 정점은 차수가 최대 $2$이며, 이는 $Q$의 모든 연결 요소가 다음 세 가지 중 하나임을 의미합니다 -
- 고립된 정점
- 간선이 $M$과 $M'$에서 번갈아 나오는 (단순) 경로
- 간선이 $M$과 $M'$에서 번갈아 나오는 짝수 길이의 사이클
$M'$의 크기가 $M$보다 크므로, $Q$에는 $M$의 간선보다 $M'$의 간선이 더 많습니다. 비둘기집 원리에 의해, 적어도 하나의 연결 요소는 $M$의 간선보다 $M'$의 간선을 더 많이 가진 경로가 됩니다. 이러한 경로는 모두 교대 경로이므로 시작 정점과 끝 정점이 $M$에 의해 포화되지 않으며, 따라서 이 경로는 $M$에 대한 증가 경로가 되고, 이는 전제에 모순됩니다. $\blacksquare$

Kuhn 알고리즘¶

Kuhn 알고리즘은 Berge 보조정리를 직접 적용한 것입니다. 이 알고리즘은 본질적으로 다음과 같이 설명됩니다:

먼저 빈 매칭에서 시작합니다. 그런 다음 알고리즘이 증가 경로를 찾을 수 있는 동안, 이 경로를 따라 매칭을 교대시켜 매칭을 갱신하고 증가 경로를 찾는 과정을 반복합니다. 그러한 경로를 더 이상 찾을 수 없게 되는 즉시 과정을 멈춥니다 - 현재 매칭이 최대 매칭입니다.

이제 증가 경로를 찾는 방법을 자세히 설명하는 일이 남았습니다. Kuhn 알고리즘은 단순히 깊이 우선 또는 너비 우선 탐색을 사용하여 이러한 경로 중 아무것이나 하나를 찾습니다. 알고리즘은 그래프의 모든 정점을 차례로 살펴보며, 각 정점에서 탐색을 시작하여 그 정점에서 시작하는 증가 경로를 찾으려고 시도합니다.

입력 그래프가 이미 두 부분으로 나뉘어 있다고 가정하면 알고리즘을 설명하기가 더 편리합니다(실제로는 입력 그래프를 명시적으로 두 부분으로 나누지 않고도 알고리즘을 구현할 수 있습니다).

알고리즘은 그래프의 첫 번째 부분에 속한 모든 정점 $v$를 살펴봅니다: $v = 1 \ldots n_1$. 현재 정점 $v$가 현재 매칭에 의해 이미 포화되어 있다면(즉, 이 정점에 인접한 어떤 간선이 이미 선택되어 있다면), 이 정점은 건너뛸 수 있습니다. 그렇지 않으면 알고리즘은 이 정점을 포화시키려고 시도하며, 이를 위해 이 정점에서 시작하는 증가 경로 탐색을 시작합니다.

증가 경로 탐색은 특수한 깊이 우선 탐색 또는 너비 우선 탐색을 사용하여 수행됩니다(구현의 편의를 위해 보통 깊이 우선 탐색을 사용합니다). 처음에 깊이 우선 탐색은 첫 번째 부분의 현재 포화되지 않은 정점 $v$에 있습니다. 이 정점에서 나가는 모든 간선을 살펴봅시다. 현재 간선을 $(v, to)$라고 합시다. 정점 $to$가 아직 매칭에 의해 포화되지 않았다면 증가 경로를 찾는 데 성공한 것입니다: 이 경로는 단일 간선 $(v, to)$로 이루어집니다. 이 경우 이 간선을 매칭에 포함시키고 정점 $v$에서 시작하는 증가 경로 탐색을 멈추기만 하면 됩니다. 그렇지 않고 $to$가 이미 어떤 간선 $(to, p)$에 의해 포화되어 있다면, 이 간선을 따라갑니다: 즉, 간선 $(v, to),(to, p), \ldots$를 지나는 증가 경로를 찾으려고 시도합니다. 이를 위해 탐색에서 정점 $p$로 이동하기만 하면 됩니다 - 이제 이 정점에서 시작하는 증가 경로를 찾으려고 시도합니다.

따라서 정점 $v$에서 시작된 이 탐색은 증가 경로를 찾아 정점 $v$를 포화시키거나, 그러한 증가 경로를 찾지 못합니다(따라서 이 정점 $v$는 포화될 수 없습니다).

모든 정점 $v = 1 \ldots n_1$을 살펴보고 나면 현재 매칭이 최대 매칭이 됩니다.

실행 시간¶

Kuhn 알고리즘은 그래프 전체에 대해 깊이/너비 우선 탐색을 $n$번 연속으로 실행하는 것으로 생각할 수 있습니다. 따라서 전체 알고리즘은 $O(nm)$ 시간에 실행되며, 이는 최악의 경우 $O(n^3)$입니다.

그러나 이 추정치는 약간 개선할 수 있습니다. Kuhn 알고리즘에서는 그래프의 어느 쪽을 첫 번째 부분으로, 어느 쪽을 두 번째 부분으로 선택하는지가 중요하다는 것이 밝혀졌습니다. 실제로 위에서 설명한 구현에서는 깊이/너비 우선 탐색이 첫 번째 부분의 정점에서만 시작되므로, 전체 알고리즘은 $O(n_1m)$ 시간에 실행됩니다. 여기서 $n_1$은 첫 번째 부분의 정점 수입니다. 최악의 경우 이는 $O(n_1 ^ 2 n_2)$입니다(여기서 $n_2$는 두 번째 부분의 정점 수입니다). 이는 첫 번째 부분의 정점이 두 번째 부분보다 적을 때 더 유리하다는 것을 보여 줍니다. 매우 불균형한 그래프($n_1$과 $n_2$가 크게 다른 경우)에서는 이것이 실행 시간의 상당한 차이로 이어집니다.

구현¶

표준 구현¶

여기서는 깊이 우선 탐색을 기반으로 하며, 두 부분으로 명시적으로 나뉜 그래프 형태의 이분 그래프를 입력으로 받는 위 알고리즘의 구현을 제시하겠습니다. 이 구현은 매우 간결하므로, 이 형태 그대로 기억해 두는 것이 좋을 수도 있습니다.

여기서 $n$은 첫 번째 부분의 정점 수이고, $k$는 두 번째 부분의 정점 수이며, $g[v]$는 첫 번째 부분의 정점에서 나가는 간선의 리스트(즉, 이 간선들이 $v$에서 이어지는 정점 번호들의 리스트)입니다. 아래 구현에서는 두 부분의 정점이 각각 독립적으로 0부터 번호가 매겨집니다. 첫 번째 부분은 인덱스 $0 \ldots n-1$을 사용하고, 두 번째 부분은 $0 \ldots k-1$을 사용합니다. 출력할 때는 이 인덱스에 1을 더합니다.

다음으로 두 개의 보조 배열 $\rm mt$와 $\rm used$가 있습니다. 첫 번째 배열인 $\rm mt$는 현재 매칭에 대한 정보를 담고 있습니다. 프로그래밍의 편의를 위해 이 정보는 두 번째 부분의 정점에 대해서만 저장됩니다. $\textrm{mt[} i \rm]$는 두 번째 부분의 정점 $i$와 간선으로 연결된 첫 번째 부분의 정점 번호입니다(해당 정점에서 나가는 매칭 간선이 없으면 $-1$입니다). 두 번째 배열은 $\rm used$로, 깊이 우선 탐색에서 정점의 "방문" 여부를 기록하는 일반적인 배열입니다(깊이 우선 탐색이 같은 정점에 두 번 들어가지 않도록 하는 용도로만 필요합니다).

함수 $\textrm{try_kuhn}$은 깊이 우선 탐색입니다. 이 함수는 정점 $v$에서 증가 경로를 찾을 수 있었다면 $\rm true$를 반환하며, 이때 이 함수는 찾은 경로를 따라 매칭의 교대를 이미 수행한 것으로 간주합니다.

함수 내부에서는 첫 번째 부분의 정점 $v$에서 나가는 모든 간선을 살펴보며 다음을 확인합니다. 이 간선이 포화되지 않은 정점 $to$로 이어지거나, 정점 $to$가 포화되어 있더라도 $\textrm{mt[}to \rm ]$에서 재귀적으로 시작하여 증가 경로를 찾을 수 있다면, 증가 경로를 찾은 것으로 보고, 결과 $\rm true$와 함께 함수에서 반환하기 전에 현재 간선을 교대합니다. 즉, $to$에 인접한 간선이 정점 $v$를 향하도록 바꿉니다.

메인 프로그램은 먼저 현재 매칭이 비어 있음을 나타냅니다(리스트 $\rm mt$를 $-1$로 채웁니다). 그다음 첫 번째 부분의 정점 $v$를 차례로 살펴보면서, 배열 $\rm used$를 미리 0으로 초기화한 뒤 그 정점에서 $\textrm{try_kuhn}$으로 깊이 우선 탐색을 시작합니다.

매칭의 크기는 메인 프로그램에서 $\textrm{try_kuhn}$을 호출하여 결과 $\rm true$를 반환한 횟수로 쉽게 얻을 수 있다는 점에 주목할 만합니다. 구하려는 최대 매칭 자체는 배열 $\rm mt$에 담겨 있습니다.

int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<bool> used;

bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    //... reading the graph ...

    mt.assign(k, -1);
    for (int v = 0; v < n; ++v) {
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

다시 한번 강조하자면, Kuhn 알고리즘은 이분 그래프임은 알려져 있지만 두 부분으로의 명시적인 분할이 주어지지 않은 그래프에서도 동작하도록 쉽게 구현할 수 있습니다. 이 경우에는 편리한 두 부분 분할을 포기하고, 그래프의 모든 정점에 대한 모든 정보를 저장해야 합니다. 이를 위해 이제 리스트 배열 $g$는 첫 번째 부분의 정점뿐만 아니라 그래프의 모든 정점에 대해 지정됩니다(물론 이제 두 부분의 정점은 $1$부터 $n$까지 공통 번호로 매겨집니다). 배열 $\rm mt$와 $\rm used$도 이제 두 부분의 정점 모두에 대해 정의되며, 따라서 이 상태로 유지해야 합니다.

개선된 구현¶

알고리즘을 다음과 같이 수정해 봅시다. 알고리즘의 메인 루프에 들어가기 전에 간단한 알고리즘(간단한 휴리스틱 알고리즘)으로 임의의 매칭을 먼저 찾고, 그다음에야 이 매칭을 개선하는 $\textrm{try_kuhn}()$ 함수를 호출하는 루프를 실행합니다. 그 결과 알고리즘은 무작위 그래프에서 눈에 띄게 빠르게 동작합니다. 대부분의 그래프에서는 휴리스틱으로 충분히 큰 매칭을 쉽게 찾을 수 있고, 그렇게 찾은 매칭을 일반적인 Kuhn 알고리즘으로 최대 매칭까지 개선하면 되기 때문입니다. 따라서 휴리스틱으로 이미 현재 매칭에 포함시킨 정점들에서는 깊이 우선 탐색을 시작하지 않아도 되므로 그만큼 시간을 절약할 수 있습니다.

예를 들어, 첫 번째 부분의 모든 정점을 단순히 순회하면서 각 정점마다 매칭에 추가할 수 있는 임의의 간선을 찾아 추가할 수 있습니다. 이처럼 간단한 휴리스틱만으로도 Kuhn 알고리즘을 몇 배나 빠르게 만들 수 있습니다.

메인 루프를 약간 수정해야 한다는 점에 유의하십시오. 메인 루프에서 $\textrm{try_kuhn}$ 함수를 호출할 때는 현재 정점이 아직 매칭에 포함되지 않았다고 가정하므로, 이에 맞는 검사를 추가해야 합니다.

구현에서는 $\textrm{main}()$ 함수의 코드만 바뀝니다:

int main() {
    // ... reading the graph ...

    mt.assign(k, -1);
    vector<bool> used1(n, false);
    for (int v = 0; v < n; ++v) {
        for (int to : g[v]) {
            if (mt[to] == -1) {
                mt[to] = v;
                used1[v] = true;
                break;
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        if (used1[v])
            continue;
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

또 다른 좋은 휴리스틱은 다음과 같습니다. 각 단계마다 차수가 가장 작은 정점(단, 고립된 정점은 제외)을 찾아, 그 정점에 연결된 아무 간선이나 선택하여 매칭에 추가한 뒤, 이 두 정점과 이들에 인접한 모든 간선을 그래프에서 제거합니다. 이러한 탐욕 기법은 무작위 그래프에서 매우 잘 동작하며, 많은 경우 최대 매칭을 구성하기까지 합니다(다만 이 방법에 대한 반례도 존재하며, 그 경우에는 최대 매칭보다 훨씬 작은 매칭을 찾게 됩니다).

참고¶

Kuhn 알고리즘은 Kuhn-Munkres 알고리즘이라고도 알려진 헝가리안 알고리즘의 서브루틴입니다.
Kuhn 알고리즘은 $O(nm)$ 시간에 동작합니다. 일반적으로 구현이 간단하지만, 최대 이분 매칭 문제에는 $O(\sqrt{n}m)$ 시간에 동작하는 Hopcroft-Karp-Karzanov 알고리즘처럼 더 효율적인 알고리즘들이 존재합니다.
최소 정점 덮개 문제는 일반 그래프에서 NP-난해입니다. 하지만 Kőnig의 정리에 따르면, 이분 그래프에서는 최대 매칭의 크기가 최소 정점 덮개의 크기와 같습니다. 따라서 이분 그래프에서는 최대 이분 매칭 알고리즘을 사용하여 최소 정점 덮개 문제를 다항 시간에 풀 수 있습니다.