일반 매칭과 응용

WM.pdf

0.23MB

유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다.

• 첫 번째는 문제 그 자체 에 대한 관심이다. 예를 들어, 택시 애플리케이션이 승객과 기사를 매칭하는 방법이나 결혼 중개업체가 남자와 여자를 짝짓는 방법 모두 이분 그래프의 매칭으로 표현할 수 있다.
• 두 번째는 이 문제가 다른 문제를 푸는데 어떻게 응용 될 수 있는지이다. 예를 들어, Konig's theorem을 사용하면 이분 그래프의 최대 매칭을 통해서 정점 덮개 (Vertex cover)를 찾을 수 있다. Dilworth's theorem을 사용하면 최소 Path cover를 이분 그래프의 최대 매칭으로 구할 수 있다. 실질적으로 문제 해결에서 중요한 건 이 부분이다.

이분 그래프에서 최대 매칭을 찾는다는 개념은 일반 그래프로도 확장할 수 있다. 매칭이라는 것은 결국 정점이 겹치지 않는 간선 집합이기 때문에, 일반 그래프에서도 정확히 동일하게 정의할 수 있기 때문이다. 굉장히 복잡한 알고리즘으로 악명이 높으나, 일반 그래프에서의 최대 매칭 역시 다항 시간에 찾을 수 있다.

이제 이 알고리즘이 왜 중요한지 알아보자. 일반 그래프에서 최대 매칭을 구하는 것 그 자체 가 중요한 이유는 다양한 예시들을 생각해 볼 수 있다. 예를 들어서, 연인 및 혼인 관계에서 생물학적 성이 중요치 않다고 생각하면, 남자와 여자라는 구분이 없어지니 이분 그래프라는 모델링을 적용할 수 없다.

한편, 일반 매칭이 다른 문제를 푸는데 어떻게 응용 되는지는 잘 알려져 있지 않다. 사실 일반 매칭을 응용한 연습 문제는 다양한 이유로 대회에 자주 출제되지 않았다. 대회에 출제되기 너무 어려운 점도 있고, 일반 매칭을 응용한 적용 예시 자체가 이분 매칭만큼 많지 않은 점도 있다. 하지만, 일반 매칭과 그것을 구하는 방법이 점차 잘 알려지고 있고, 일반 매칭을 적용한 사례들 중에서는 상당히 아름답고 생각하기 어려운 예시들이 많아, 어느 정도는 배울 가치가 있다고 생각한다. 이 글에서는 일반 매칭을 응용해서 풀 수 있는 다양한 문제의 예시를 설명하려고 한다.

알고리즘

Tutte Matrix

다른 알고리즘에 비해서 구현과 이해가 압도적으로 쉬운 알고리즘이 있는데, 바로 Tutte matrix를 사용하는 것이다. Blossom을 이해하지 않는 이상, 팀노트가 금지되었거나, 팀노트에 매칭 알고리즘이 없을 경우에도 쓸 수 있는 유일한 방법이다.

그래프 $G = (V, E)$ 가 주어졌을 때, 랜덤한 소수 $p$를 고르고 (해싱하듯이 적당히 고르면 된다) 다음과 같은 $|V| \times |V|$ 행렬 $T$ 를 만들자.

$T_{i, j} = \begin{cases} r_{i, j} & \mbox{if } (i, j) \in E \mbox{ and } i < j \newline -r_{j, i} & \mbox{if } (i, j) \in E \mbox{ and } i > j \newline 0 & \mbox{otherwise}\end{cases}$

$r_{i, j}$ 는 변수로, 무슨 값이 올지는 정해져 있지 않다. 이제 알고리즘은 다음과 같다. $r_{i, j}$ 에 $[1, p-1]$ 사이의 랜덤 정수를 부여하고, Gaussian elimination을 통해서 (mod $p$ 에서) $rank(T)$ 를 구하면, $G$ 의 최대 매칭의 크기는 높은 확률로 $\frac{rank(T)}{2}$ 이다. 시간 복잡도는 당연히 $O(n^3)$ 이고, 상수도 작은 편이다. 다만 이 방법으로는 실제 매칭이 무엇인지 알 수 없다.

이 사실의 증명은 이 글을 참고하면 알 수 있다. 이 글에서는 전체 증명을 소개하지는 않고, 증명의 일부만 소개한다. 알고리즘에 대한 직관을 얻는 데는 이 정도로 충분하다고 생각하기 때문이다.

• Theorem. $G$ 에 Perfect Matching이 있음과, $\det T \neq 0$ 임이 동치이다.
• Proof.
  • $\rightarrow$: $\det T = \sum_{p \in P_n} (-1)^{inv(p)} \Pi_{i \in [n]} T_{i, p_i}$ 이다. 이 때 $P_n$ 은 모든 길이 $n$ 의 순열의 집합이다. $p_i$ 를 $i$ 와 매칭된 반대쪽 정점이라고 정의하자. $p$ 는 자명히 순열이며, 이 순열은 모든 매칭에 속하는 간선 $(u_1, v_1), \ldots, (u_{n/2}, v_{n/2})$ 에 대해 $\Pi_{i \in [n/2]} T_{u_i, v_i}^2 (-1)^{inv(p)}$ 가 된다. $\Pi_{i \in [n/2]} T_{u_i, v_i}^2$ 이 등장하는 다른 항은 $\det T$ 에 없다.
  • $\leftarrow$: 모든 순열 $p$ 에 대해서, 이들이 얼마나 $\det T$ 에 기여하는지 살펴보자. 순열은 방향성이 있는 사이클의 집합으로 분해할 수 있다. 만약에 해당 순열에 $p_i = i$가 있다면 이 순열은 $\det T$ 에 기여하지 않는다. 만약 순열에 홀수 길이의 사이클이 있다면, 이 사이클의 방향을 뒤집어보자. $(-1)^{inv(p)}$ 는 그대로 남지만 $r_{i, j}$ 가 $-r_{j, i}$ 로 바뀌어서 서로가 서로를 취소한다. 고로 짝수 사이클과 매칭의 집합으로 이루어진 순열들만 $\det T$ 에 기여하고, $\det T \neq 0$ 이면 이러한 순열이 존재한다는 것이다. 고로 이러한 순열 하나를 고른 후, 매칭은 그대로 두고, 짝수 사이클 상에서 번갈아가면서 간선을 고르면 된다.

마지막으로 이렇게 행렬식을 사이클들의 집합으로 생각해서 계산하는 아이디어는 그래프와 결합했을 때 꽤 유용한 편이다. 매칭이나 Dynamic Programming 같은 잘 알려진 조합적 컨셉을 통해서 대수적인 문제를 해결할 수 있기 때문이다. 이러한 식의 아이디어를 사용한 문제들도 몇 개 있다. BOJ에 Determinant로 검색하면 나오는 위의 세 문제를 참고하라.

General Algorithms

일반적으로 Maximum Unweighted Matching을 계산하는 잘 알려진 방법은 Edmond's Blossom Algorithm으로, 시간 복잡도 $O(n^2 m)$ 에 작동하는 알고리즘이다. 일반 매칭을 구하는 거의 모든 알고리즘은 여기서 나온 Blossom 개념을 활용하기 때문에, 모든 것의 시작이 되는 알고리즘이다. 이 알고리즘은 느리며, 구현도 복잡하기 때문에, 여기서는 다루지 않는다.

이 GitHub 링크에는 General Matching을 구현하는 크게 4가지의 코드가 있다. 각 코드에 대해서 설명한다.

• matching_short.cpp 는 Maximum Unweighted Matching을 $O(n^3)$ 에 계산한다. 상수는 작은 편이다. $O(nm)$ 이라는 이야기도 나왔으나 반례가 있다고 기억하고 있다 (해당 반례를 찾으면 다시 수정하도록 하겠다). Blossom algorithm에서 사용하는 Shrinking을 명시적으로 구현하지 않음으로서, 거의 이분 매칭에 준할 정도로 코드가 짧다. 관련해서는 알고리즘을 구현한 HYEA가 쓴 이 글을 참고하면 좋다.

• matching.cpp 는 Maximum Unweighted Matching을 $O(m \sqrt n \log n)$ 에 계산한다. $\log$ 는 Union-find에 의해서 붙는다고 알고 있다. 여기 있는 구현은 min_25 이라는 분이 The Weighted Matching Approach to Maximum Cardinality Matching 에 나온 방식으로 구현하였다.

• matching_weighted_dense.cpp 는 Maximum Weighted Matching을 $O(n^3)$ 에 계산한다. 코드가 긴 편이나 팀노트에 넣을 수 있는 수준이다. Hungarian Algorithm 대용으로 사용해도 그다지 느리지 않을 정도로 상수는 작은 편이다 (재 본 것은 아니니 정말 대용으로 쓰고 싶으면 확인해 보자). 실제로 Primal-dual method라서 Hungarian Algorithm을 응용한 것이라고 알고 있다. 이건 중국에서 돌던 코드인 것 같은데 원작자가 누구인지 모른다.

• matching_weighted_sparse.cpp 는 Maximum Weighted Matching을 $O(nm \log n)$ 에 계산한다. 고로 Sparse graph에서 위 알고리즘보다 빠르다. 코드는 dense 에 비해서 굉장히 긴 편이다. 이 코드 역시 min_25가 구현하였으며 기반이 된 논문은 이것이라고 한다.

이것보다 더 빠른 알고리즘들에 대해서 코멘트를 하자면

• Unweighted Matching은 $\log$ 없이 $O(m \sqrt n)$ 에 계산할 수 있으나, $\log$ 가 없는 거지 Union-find가 없는 것이 아니기 때문에 실질적으로는 위에 있는 코드들도 state-of-the-art에 가깝다. $O(m \sqrt n)$ 에 매칭을 구하는 최초의 알고리즘은 1980년 발표된 Micali-Vazirani이고, 이후 여러 알고리즘들이 알려졌다.
• 2017년 Duan, Pettie, Su는 Scaling Algorithms for Weighted Matching in General Graphs 이라는 논문을 통해서 $O(E\sqrt V\log(\sum W))$ 시간에 작동하는 Weighted Matching 알고리즘을 발표했다. 좋은 구현체를 본 적은 없다. 관심있는 사람은 일독을 권한다.
• 간선 추가 / 제거 쿼리가 들어올 때 Approximate Matching을 관리하는 논문들이 있다.

응용 문제

TooSimple이 코드포스에 올린 글을 참고하여 연습문제를 작성한다.

문제에서 얘기하는 그래프 는 방향성이 없고, 루프와 중복 간선이 없고, 연결되어 있으며, 모든 간선에 양의 정수 가중치 $w: E \rightarrow \mathbb{Z}_{>0}$ 가 있다. (가중치를 사용하지 않는 문제들도 있다.)

풀이는 "더 보기" 를 누르면 나온다. 티스토리에서 마크다운과 함께 지원을 하지 않아 부득이하게 접기는 생략한다.

1. Chinese Postperson Problem

그래프가 주어졌을 때, 모든 간선을 최소 한 번 방문하는 최소 길이의 회로를 찾아라. 회로는 시작점과 끝점이 같으며, 방문한 정점과 간선을 다시 방문해도 되는 사이클을 뜻한다.

Christofide's Algorithm의 서브루틴으로 잘 알려진 문제다. (이에 대해서는 위에 첨부한 슬라이드를 참고하라.)

모든 차수가 짝수인 그래프일 경우에는 Euler Circuit을 구하면 되니까, 답이 $\sum_{e \in E}w(e)$ 이다. Euler Circuit의 조건은 매우 깔끔하니, 문제의 조건을 Euler Circuit에 맞게 변형하자.

문제에서는 간선을 한 번 이상 방문해야 하고, 사이클의 길이를 최소화해야 한다. 반대로 간선을 정확히 한 번 방문해야 하고, 대신 그래프에 있는 간선을 복제해서 복제한 후의 그래프의 간선 가중치 합을 최소화하는 문제로 생각할 수 있다. 간선을 정확히 한 번 방문하기 위한 조건이 바로 Euler Circuit이니, 그래프에 있는 간선을 적당히 복제해서 모든 정점의 차수를 짝수로 만들어야 할 것이다. 여기서, 한 간선을 두 번 이상 복제할 필요가 없음이 ($n$ 번 복제하는 대신 $n-2$ 번 복제해도 같음) 확인된다. 비슷한 이유로, 복제한 간선의 집합이 사이클을 가지지 않음 (사이클 전체를 지워줘도 됨) 알 수 있다.

이제 다른 식으로 문제를 보자. 만약에 그래프에 홀수 차수의 정점이 2개라면, 우리는 두 정점간의 최단 경로를 복제하면 된다. 만약에 그래프에 홀수 차수의 정점이 $2n$ 개라면, 적당히 각 홀수 차수의 정점을 짝지어준 후, 그들간의 최단 경로를 복제해주는 식으로 할 수 있다. 이렇게 보면 이 문제를 매칭의 관점으로 생각해 줄 수 있다. 홀수 차수의 정점들을 모아준 후, 각 정점을 매칭하는 비용을 둘 간의 최단 경로로 정의한 후 최소 가중치 매칭을 찾는다. Floyd-Warshall을 사용하면 모든 쌍 최단 경로를 찾을 수 있고, 전체 문제가 $O(N^3)$ 정도에 풀린다.

확실히, 이렇게 매칭을 통해서 찾은 해는 가능한 해 중 하나이다. 그렇다면, 이 해가 과연 최적일까? 이것이 최적임을 증명하기 위해, 우리는 모든 해가 홀수 차수 정점들을 양 끝점으로 하는 edge-disjoint한 path들의 집합 으로 표현될 수 있음을 보인다.

위에서 관찰했듯이, 이 문제의 최적해는 사이클을 포함하지 않는다. 최적해의 어떤 비자명한 컴포넌트를 고르면, 최소 2개의 리프 정점이 있을 것이다. 이들간의 unique path를 찾아서, 지워주자. 이 때 path의 내부 정점은 차수가 2씩 바뀌기 때문에, parity가 변하지 않는다. 이것을 계속 반복하면 모든 비자명한 컴포넌트를 지워줄 수 있고, 위에서 원하는 집합으로 분리를 할 수 있어서, 문제가 해결된다.

2. Weighted Edge Cover

차수가 0인 정점이 없는 그래프가 주어졌을 때, Edge Cover 는 모든 정점을 덮는 간선의 부분집합을 뜻한다 (즉, 모든 정점이 부분집합에 속하는 간선의 끝점 중 하나임). 최소 가중치 Edge Cover를 구하여라.

가중치가 모두 1일 때, Edge Cover 문제의 답은 $V - M$ 임이 잘 알려져 있다 ($M$ 은 최대 매칭의 크기이다). 이유는 다음과 같다.

Lemma. Edge Cover의 최적해에는, 길이 3의 경로가 없다.

Proof. 있다면, 중간에 있는 간선을 제거하면 모순이다.

Lemma에 의해, Edge Cover는 서로 겹치지 않는 성게 (star graph) 들이 모든 정점을 덮고 있는 형태임을 알 수 있다. 최대 매칭이 주어졌을 때, 모든 정점은 매칭에 있거나 매칭에 있는 임의의 정점과 인접하다 (그렇지 않다면 차수가 0이거나 매칭을 늘려줄 수 있음). 고로 $V - M$ 크기의 해를 찾을 수 있다. 한편, 크기 $V - M$ 의 해가 존재한다면, $M$ 개의 성게 컴포넌트가 존재하니, 이들에서 간선을 하나씩 뽑으면 크기 $M$ 의 매칭을 찾을 수 있다. 고로 증명이 끝난다.

Weighted Edge Cover에서도 비슷한 형태의 답을 유도해 보자. 하지만 첫 장부터 막히기 시작한다. 간선 하나의 cost가 1이 아닌데 어떻게 $V$라고 쓸 수가 있을까? 성급하게 내릴 수 있는 결론 하나는, 해당 정점에서 나가는 가장 가중치가 작은 간선을 고르고, $V$를 $\sum_{v \in V(G)}{\omega(v)}$ 로 대체하는 것이다. $\omega(v)$ 는 각 정점에 대한 최소 가중치 간선의 무게로 정의된다.

Edge Cover의 형태를 관찰해 보면, 서로 겹치지 않는 성게 (star graph) 들이 모든 정점을 덮고 있는 형태임을 알 수 있다. 재미있는 관찰은, 성게의 리프 (degree가 1) 정점이 연결된 루트는, 해당 리프에서 가장 가중치가 작은 간선으로 연결된 정점이라는 것이다. 즉 루트를 $R$, 리프 하나를 $l$ 이라고 하면, $\omega(l) = weight(R, l)$ 이다. 증명은 간단한 귀류법이다.

성게는 서로 겹치지 않기 때문에, 각 성게에서 임의의 간선을 하나씩 뽑으면 무조건 매칭이다. 그러면, 다음과 같은 해결법을 생각해 보자: 모든 매칭을 고려하는데, 매칭에 포함되지 않은 정점들은, 해당 정점과 연결된 최소 가중치 간선으로 붙이는 식으로 모든 정점을 덮는 것이다. 임의의 최적해를 생각해 보면, 최적해에서 고른 임의의 "매칭" 에 포함되지 않은 정점들은 모두 위와 같은 방법으로 붙일 수 있다. 고로 임의의 최적해가 고려된다. 한편, 이 방식으로 열거한 해들은 Edge Cover이기 때문에 최적해보다 작은 답이 고려되지는 않는다.

결과적으로, 매칭 $M$에 대해 답은 $\sum_{v \in V(G)}{\omega(v) }- \sum_{(u, v) \in M}{(\omega(u) + \omega(v) - weight(u, v))}$ 이다. 간선의 가중치를 위 식으로 대체한 후 Max Weighted Matching을 돌리면 된다.

3. Undirected Vertex Geography

Alice와 Bob은 그래프에서 게임을 하고 있다. Alice가 먼저 시작하고 각 플레이어가 번갈아가며 턴을 진행한다. 맨 처음 그래프의 특정 정점 $v$ 에는 토큰이 놓여 있다 ($v$ 는 주어진다). 플레이어들은 차례로 토큰을 인접한 정점으로 옮기는데, 한번 토큰이 있었던 위치를 다시 방문할 수는 없다. 움직일 수 없는 플레이어는 패배한다. 누가 이기는지 판단하라.

이 문제는 이분 그래프에서도 잘 알려진 문제이고, 일반 그래프에서도 동일한 방법으로 해결된다.

$v$ 를 포함하지 않는 최대 매칭이 있음과, Bob이 이길 수 있음이 동치이다.

• 그러한 매칭이 있음: 이를 $M$ 이라 하자. Alice는 $v$ 에서 처음 움직일 때 무조건 $M$ 에 속하는 정점으로 움직이게 된다. 만약 그렇지 않을 수 있다면 $M$ 에 해당 간선을 넣으면 최대 매칭이 아니기 때문이다. Bob은 이제 해당 정점에 매칭된 정점으로 움직이는 것을 반복하는 전략을 사용하면 된다. 만약 Alice가 해당 전략에서 벗어나기 위해서는 $M$ 을 탈출해야 하는데, 이 경우 $v$ 에서 시작해서 탈출하기까지의 경로를 잡은 후, 이 경로와 $M$ 의 symmetric difference를 취하면 $M$ 보다 크기가 하나 더 큰 매칭을 찾을 수 있다.
• 그러한 매칭이 없음: Alice는 $v$ 를 포함하는 최대 매칭 $M$ 을 찾고 위와 같은 전략을 택할 수 있다. Bob이 해당 전략에서 벗어나기 위해서는 $M$ 을 탈출해야 하는데, 이 경우 $v$ 에서 시작해서 탈출하기까지의 경로를 잡은 후, 이 경로와 $M$ 의 symmetric difference를 취하면 $v$ 를 포함하지 않는 최대 매칭을 찾을 수 있다.

4. Parity Shortest Simple Path

두 정점 $s, t$ 와 $p \in {EVEN, ODD}$ 이 주어진다. $s$와 $t$를 잇는 경로 중, 간선의 개수가 홀수/짝수개인 가장 짧은 경로를 찾아라. 이 때 경로는 중복해서 방문하는 정점이 없어야 한다.

중복해서 방문하는 정점이 있어도 된다고 하면, 문제를 어렵지 않게 해결할 수 있다. $G$의 복사본 $G^\prime$를 만든 후, 모든 간선 $e = {u, v}$ 에 대해서 $G(u) \leftrightarrow G^\prime(v)$, $G(v) \leftrightarrow G^\prime(u)$ 를 잇자. 그렇다면, $G$ 와 $G^\prime$ 을 잇는 임의의 경로의 길이는 홀수이고, 같은 그래프 간을 잇는 임의의 경로의 길이는 짝수이다. 고로, $G(s), G(t)$ 혹은 $G(s), G^\prime(t)$ 간의 최단 경로를 Dijkstra's algorithm 등으로 찾아주면 된다.

단순 경로 를 찾아야 한다면 위와 같은 접근이 통하지 않는데, 놀랍게도 일반 매칭을 사용하면 문제를 해결할 수 있다. 사실 어떻게 매칭이 도움이 된다고 생각할 수 있었는지 잘 모르겠다. 딱히 직관이 없어서 풀이만 설명한다.

일반성을 잃지 않고 짝수 길이의 경로를 찾는다고 하자 (홀수도 똑같이 하면 된다). $G$의 복사본 $G^\prime$를 만드는 것까지는 동일하게 하지만, 모든 간선 $e = {u, v}$ 에 대해 $G(u) \leftrightarrow G(v)$, $G^\prime(u) \leftrightarrow G^\prime(v)$ 를 이어준다. 다른 편을 잇는 것이 아니라 같은 편을 잇는 것이다. 마지막으로, 모든 정점 $v \in V$에 대해 $G(v) \leftrightarrow G^\prime(v)$ 간의 정점을 이어준다. 이 그래프에서 완벽 매칭을 찾으면, 원래 그래프 $G$ 의 정점들은 $G(v) \leftrightarrow G^\prime(v)$ 를 잇는 간선으로 덮여 있거나, $G, G^\prime$ 을 오가는 짝수 사이클에 포함될 것이다.

이제 $G(s), G^\prime(t)$ 를 지우고 완벽 매칭을 구해주자. $G^\prime(s)$ 에서 매칭된 정점 $v$ 로 이동한 후, 사이드를 뒤집고, 같은 방식으로 계속 매칭된 정점을 따라서 이동하자. 이 과정 상에서 $G(v) \leftrightarrow G^\prime(v)$ 를 잇는 간선은 절대 만날 수 없고, 이 과정은 $t$ 에 도달하지 않으면 끝나지 않으며, 이 과정은 무조건 종료하게 되어 있다. 경로 상에서 만났던 정점들을 나열하면 간선이 짝수개인 경로를 찾을 수 있다. 이렇게 해서 $s$ 와 $t$ 를 잇는 Parity shortest path의 존재성을 확인할 수 있다. 최솟값을 찾는 것은, $G(v) \leftrightarrow G^\prime(v)$ 를 잇는 간선의 가중치는 0, 나머지는 원래 간선의 가중치로 주면 된다.

5. Planar Graph Max Cut

그래프가 주어졌을 때, 정점 집합을 두 개의 비지 않은 부분집합으로 분할하자 ($S, V\setminus S$). 이 때, 두 부분집합 사이를 잇는 간선의 개수를 최대화하라. (Global Min Cut은 이 값을 최소화한다.)

Global Min Cut의 답이 0인 경우는 그래프가 연결되지 않았을 때이지만, Global Max Cut의 답이 간선 전체의 개수인 경우는 그래프가 이분 그래프 일 때이다. 다른 말로, Max Cut은 그래프에서 최소의 간선을 지워서 그래프를 이분 그래프로 만드는 문제이다.

Planar Graph가 이분 그래프면 어떤 성질이 있을까? Planar graph는 Dual이라는 매우 유용한 개념이 있다. 평면 그래프의 Dual은 간선 집합은 똑같은데, 정점 집합이 면으로 바뀐다. 이 때 각각의 면은 cycle이고, 이분 그래프는 홀수 사이클이 없으니, 각 사이클은 짝수 개의 간선에 인접했다. 즉, Planar Graph가 이분이면, Dual의 모든 정점의 차수는 짝수이다. 다른 말로 오일러 회로가 존재한다.

여기까지 왔으면 문제가 거의 Chinese postperson Problem이랑 동일해 보이는데, 약간의 차이점이 있다. Chinese postperson problem에서는 있던 간선을 복제하는 것이고, 여기서는 두 면 사이를 분리하는 간선을 압축(contract)해서 두 면을 합쳐주는 연산을 한다는것이다. 일단, 두 정점을 합쳐주는 연산이라고 생각하더라도, Dual graph에 대해서 postperson problem과 같은 식으로 최소 가중치 매칭을 찾아준 후 매칭에 들어간 간선들을 합쳐주면 그것은 가능한 해가 된다. 차수가 $x, y$ 인 두 정점을 합쳐주면 새로운 정점의 차수는 $x+y-2$ 가 되고, 위와 같은 식으로 연산을 하면 매칭된 두 홀수 차수 정점은 하나의 정점으로 합쳐지기 때문이다. 이제 이것이 최적해인 것을 보여야 하는데, 이것은 1번 문제에서 사용한 증명법을 완전히 동일하게 사용하면 된다.

6. NEERC 2018 B

당신은 기계와 노동자가 있는 공장을 운영하고 있다. 노동자 $i$ 가 기계 $j$ 를 다룰 수 있는가에 대한 관계는 이분 그래프의 형태로 주어진다.

각 기계는 정확히 두 명의 노동자가 다뤄야 한다. 각 노동자는 최대 1개의 기계를 다룰 수 있다. 최대한 많은 기계를 작동시키는 배정을 찾아라.

노동자가 두 명이 아니라 한 명이면 이 문제는 정확히 이분 매칭 문제이다. 고로 유사한 이분 그래프를 정의하려 해 보자. 한 가지 가능한 아이디어는, 하나의 기계에 대해서 두 개의 동일한 정점을 만들고, 여기서 이분 매칭을 구하는 것이다. 이상적으로는, 이렇게 할 경우 두 개의 정점에 서로 다른 노동자가 매칭이 될 것이니, 이분 매칭의 크기가 $M$ 이면 답은 $\frac{M}{2}$ 가 될 것이다.

물론 이 아이디어는 틀렸다. 두 개의 정점 중 하나의 정점만 매칭이 될 경우, 해당 기계는 작동되지 않으나, $\frac{1}{2}$ 만큼 답에 기여한다는 것이다. 이러한 기계를 반작동 하는 기계라고 하자.

이를 위해서, 모든 기계가 기본적으로 반작동 하게 하고, 작동 하는 기계의 개수를 최대화한다. 한 기계에 대해서 만들어 준 두 개의 정점 간에 간선을 추가한다. 이제, 어떠한 노드에

• 0명의 노동자가 매칭되었다면, 기계는 자기 자신을 잇는 두 노드를 매칭시키면 되고, 답에 1씩 기여한다 (반작동)
• 1명의 노동자가 매칭되었다면, 기계는 노동자와 자신을 잇는 매칭을 끊고, 자기 자신을 잇는 두 노드가 매칭되었다고 생각하면 된다. 고로 이 역시 답에 1씩 기여한다 (반작동)
• 2명의 노동자가 매칭되었다면 기계는 답에 2씩 기여한다.

고로, 답은 이 그래프에서의 (최대 매칭의 크기) - (기계의 개수) 가 된다.

7. UOJ 171

당신은 기계와 노동자가 있는 공장을 운영하고 있다. 노동자 $i$ 가 기계 $j$ 를 다룰 수 있는가에 대한 관계는 이분 그래프의 형태로 주어진다.

각 기계는 정확히 한 명의 노동자가 다뤄야 한다. 각 노동자는 최대 3개의 기계를 다룰 수 있다. 여기서는 조건이 특이하다. 모든 기계를 작동시키는 배정 중, 0개 혹은 1개의 기계를 다루는 노동자의 수를 최대화하는 배정을 찾아라. 모든 기계를 작동시키는 배정이 없을 경우 없다고 판별하라.

각 노동자를 두 개의 노드로 분할하자. 한 노동자는 0개 혹은 2개의 기계를 다루고, 다른 노동자는 0개 혹은 1개의 기계를 다룬다. 이렇게 하면, ${0, 1, 2, 3}$ 개의 선택을 전부 표현할 수 있다. 이제 문제는, 모든 기계를 작동시키면서, 첫번째 종류의 노동자를 최소로 사용하는 배정을 찾는 것이다.

첫 번째 종류의 노동자만 존재하면, 이 문제는 6번 연습 문제와 같고, 두 번째 종류의 노동자만 존재하면, 이 문제는 이분 매칭 문제이다. 고로, 첫 번째 종류의 노동자를 6번 문제와 같은 형태로 배치하고, 두 번째 종류의 노동자는 일반적인 이분 매칭 형태로 배치하자. 이제 우리는 첫 번째 종류의 노동자를 최대한 반작동 상태로 두면서 모든 기계를 덮어야 한다.

이제, 기계와 노동자를 잇는 노드들은 가중치 $INF$ 를 주고, 노동자 간을 잇는 노드들은 가중치 1을 주자. 여기서 최대 가중치 매칭을 찾으면, $INF$ 간선을 최대한으로 사용하면서, 그 다음으로 노동자 간을 잇는 노드의 개수를 최대화할 것이다. $INF$ 간선 하나는 기계 하나를 덮는다. 고로 이것은 모든 기계를 덮으려고 하면서 노동자 간을 잇는 노드 개수를 최대화한다. 답은 $WeightedMatching - N \times INF$ 이 되고, 이 값이 음수면 배정이 존재하지 않는다.

8. Min Cost Disjoint Cycle Cover

그래프가 주어졌을 때, Disjoint Cycle Cover 는 모든 정점을 덮으며, 사이클 간에 정점이 겹치지 않는 (vertex-disjoint) 사이클의 집합을 뜻한다. 이 때 사이클은 길이가 3 이상이다. 최소 가중치 Disjoint Cycle Cover를 구하여라.

그래프에서 Disjoint Cycle Cover만 남기면, 모든 정점의 차수가 2이다. 반대로, 모든 정점의 차수가 2인 간선 부분집합을 가져가면, 이것이 Disjoint Cycle Cover라는 것을 알 수 있다. 중복 간선이 없기 때문에, 길이 2인 사이클이 존재할 수 없기 때문이다. (이것은 일반적으로 성립하는 논리이다: 만약에 중복 간선이 있는 그래프가 주어지면, 가중치가 가장 작은 간선만 남기자.)

이제 이 문제를 플로우와 비슷하게 모델링할 수 있다. 각 간선과 정점에 대해서, 그에 대응되는 노드를 만들자. 모든 정점은 2개의 서로 다른 간선과 매칭되어야 하고, 일부 간선은 두 양 끝점과 매칭되어야 한다. 각 정점과 간선에 대해서 용량 2의 간선을 source/sink랑 이어주고, 모든 간선에 대해서 양 끝점으로 용량 1의 간선 두 개를 이어주자. 이 그래프에서 최대 유량이 $2|V|$ 인지 찾아주면 될까? 용량 2의 간선을 1로 사용할 수 있는 경우가 존재하기 때문에, 답을 구할 수 없다.

플로우 접근이 실패했으니, 매칭으로 돌아가보자. 일단 정점과 간선에 대한 demand가 2이니 각 정점에 대해서 2개 ($v, \bar{v}$), 간선에 대해서 2개 ($e_{i, u}, e_{i,v}$) 로 노드를 복사해 주자. 이들 정점을 잇는 간선은 각 간선마다 $(u, e_{i, u}), (\bar{u}, e_{i, u}), (v, e_{i, v}), (\bar{v}, e_{i, v})$ 와 같이 4개가 있다. 이 그래프는 사실상 위의 플로우 그래프와 동일한 형태이고, 각 간선에 대해서 양 끝점 중 하나만 매칭될 수 있다는 동일한 문제로 인해서 답을 구할 수 없다.

사실 이 문제는 6/7에서 겪었던 문제와 동일하니, 위에서 사용한 반작동 과 비슷한 컨셉을 도입하자: 모든 간선 $e = {u, v}$에 대해서, $e_u, e_v$ 간에 간선을 이어주고, 이들간의 매칭이 형성되었다는 것은 이 간선을 무시한다는 뜻이라고 간주하자. 이 그래프에서 완벽 매칭이 존재한다는 것은, 모든 정점에 대해서 2개의 인접한 간선과 매칭이 되었고, 모든 간선에 대해서 양 끝점이 서로 매칭되었거나 (간선이 무시되었거나) 아니면 정점에 짝지어져 있다는 것이다. 고로, 완벽 매칭이 존재한다는 것과 Disjoint Cycle Cover가 존재한다는 것은 동치이다.

이제 가중치를 줘야 하는데, $(e_u, e_v)$ 를 잇는 간선에는 $w_i$ 의 가중치, 나머지는 0의 가중치를 주자. 최대 가중치 매칭을 찾은 후, 모든 간선의 가중치 합에서 매칭의 비용을 빼 주면 된다.

9. Two Matching

그래프가 주어졌을 때, 최대 가중치의 간선 부분집합을 골라서, 모든 정점이 해당 부분집합에 속하는 간선과 최대 2개 인접하도록 하라. (최대 1개 인접하도록 한다면 이 문제는 General Matching이 된다.)

모든 정점의 차수가 2 이하인 연결 그래프는 빈 정점, 경로, 사이클 뿐이다. 고로 2-matching의 각 컴포넌트는 정점 하나거나, 경로거나, 사이클일 것이다. 경로의 양 끝점을 간선으로 이어주고, 모든 정점마다 루프를 만들어주면, 이것은 Disjoint Cycle Cover가 된다. 사이클의 길이가 3 이상이라는 조건을 제외하면 말이다. 고로

• 모든 서로 다른 정점 쌍에 대해서, 가중치 0인 간선을 만들어주자. 이제 경로 컴포넌트는 Disjoint Cycle Cover에서 사이클이 된다. 가중치 0인 간선이 선택되었다면, 그냥 빼 줘도 2-matching에 위배되지 않는다.
• 루프는 직접 만들어주지 않고, $v, \bar{v}$ 간에 가중치 0인 간선을 만들어주는 것으로 대체하자.

이제, 이 그래프에서 Disjoint Cycle Cover를 구하면 된다. 사이클의 길이가 3 이상이라는 조건에 걱정할 필요는 없다: 8번 문제의 construction은, 중복 간선이 들어왔을 때, 길이 2인 사이클을 찾게끔 되어 있다 (증명한 방식을 생각하면 자명하다).