[Graph Theory] Matchings - Bipartite and general graph

job assignment problem 을 생각해보자.

총 n 개의 job 이 있고, set $A$ 만큼의 지원자가 있다고 하자.

$A$ 중에서 $A_i$ 가 $i$ 번째 직종에 지원 가능하다고 했을 때, 

$A_1$ 부터 $A_n$ 까지 각각 한명씩 매칭시킨 $x_1$ 부터 $x_n$ 을 찾을 수 있다.

이게 대표적인 system of distinct representatives <SDR> 문제.

 

Definition.

A matching: a set of pairwise non-incident edges (independent edges): vertex가 안겹치는 edge 들의 set.

matching covers the vertices: matching 에 포함되는 edge 들에 닿은 vertex 들.

perfect matching: 그래프의 모든 vertices 를 커버하는 matching: vertex를 싹 다 포함하는 matching

matching number $\alpha'(G)$: maximum size of a matching: matching이 가장 클 때 그 안의 edge 갯수.

 

4.1. Matching in bipartite graphs

bipartite 그래프는 언제 perfect matching 을 가지는가?

어떤 조건에서 모든 vertex 를 싹 다 커버하는 matching 을 가지는가?

$N(S) = \cup_{v \in S} N(v)$ 라는 notation 을 염두에 두고 조건을 찾아보자.

 

Theorem. <Hall's Theorem>

X,Y-bigraph 에서,

X를 cover하는 매칭이 존재한다 $\Leftrightarrow$ $|N(S)| \geq |S|$ for all $S \subseteq X$

X중에 아무렇게나 애들을 뽑아놔도 그들의 친구들이 더 많은 상황이면, 일단 X는 싹다 커버 가능하다. 그 역도 성립.

$\textit{Proof}$

Neccesity <$Rightarrow$> 는 간단하니까 패스.

$Leftarrow$:  induction 을 쓰자.

$|X| = 1$일 때는 확실. $|N(X)| \geq |X|$ 면 당연히 X는 하나밖에 없으니까 다 매칭 되겠지.

$|X| >1$ 인 상태로 $|N(S) > |S|$인 경우:

일단 $x \in X$ 에 대해서 $y \in N(x)$ 는 무조건 있다. <by Hall's condition> <  $|N(S) > |S|$ 로 가정 해놨으니까>

그럼 $G - \{x, y\}$ 도 Hall's condition 성립이야. 왜냐하면 $x$ 빼고 $X - \{x\}$ 에서 subset 을 아무리 잡아도 $Y$ 에서는 최대 한개 $y$ 밖에 안빠졌으니까 $N(S)$ 가 작아질 수가 없음.

Induction 을 진행하다 보면 $X-\{x\}$ 랑 $xy$ 가지고 perfect matching 할 수 있다. 하나씩 빼주는 걔들이 perfect matching 이다 이거지.

$|X| >1$ 인 상태로 $|N(S) = |S|$인 경우:

$S \cup N(S)$, S랑 S친구들로 이루어진 그래프 $G_1$.

$V(G) \backslash (S \cup N(S))$, 그리고 나머지 쩌리들로 만든 그래프 $G_2$

일단 G_1 한테는 Hall's condition 이 성립한다. $G_2$에 대해서 체크하기 위해서 $T \subseteq X \backslash S$  를 따져보면

$N_{G_2}(T) = N_G(T \cup S) - N_G(S)$

$G_2$ 에서 $T$의 친구들은 $G$ 일 때 $T$ 랑 $S$ 무리 중에서 $S$ 무리 친구들 뺀 거다.

$|N_{G_2}(T)| = |N_G(T \cup S)| - N_G(S)| \geq |T \cup S| - |S| = |T|$

$G$에 대해서 $T \cup S$ 랑 $S$ 가 Hall\s condition 이 성립하니까 $T$에 대해서도 성립한다.

G_1, G_2 가 성립하니 Induction 을 써서 $S$ 와 $X \backslash S$ 에다가 각각 쓰면 그 union 이 desired matching 이다.

 

Corollary. <Marriage theorem>

모든 nontrivial regular bipartite multigraph 는 perfect matching 을 가진다.

bipartite multigraph 가 regular 하면 vertex 남김없이 matching 가능하다.

$\textit{Proof}$

$S \subseteq X$ 에 대해서 $k|S| \leq k|N(S)|$ 다.

$S$ 쪽에서 각자 $k$ 개씩 던졌는데, $N(S)$ 는 받기도 하지만 일단 자기네들도 $k$개씩 던질테니까 당연히 더 크다. 그러니까 $|S| \leq |N(S)|$ 가 성립되면서 perfect matching.

 

Corollary.

X,Y-bigraph 에서 

$\alpha'(G) = min_{S \subseteq X} \{\X| - (|S|-|N(S)|) \}

가장 매칭이 많을 때에는 매칭을 못한 애들이 가장 적을 때다.

$\textit{Proof}$

$S$ 에서 짝을 찾아 나섰을 때, 가장 "슬픈" 케이스는 $N(S)$ 가 적을 때. 그러니까,

$|S|-|N(S)|$ 가 클 때 가장 '슬프다'.

$d = max_{S \subseteq X}\{|S|-|N(S)| \}$ 여서, 매칭이 아주 크게 망한 케이스를 d라고 치자.

사실 우리는 $|X| -d$ 만큼의 매칭을 만들어줄 수 있다.

패자부활전을 위해, $Y$ 에다가 $d$만큼의 추가 투입을 해주자. 그리고 걔들이 $X$랑 모두 짝을 맺도록 하고 새로운 그래프 $G'$을 만들었다고 치자.

그 $G'$ 은 (꿈일 뿐이지만) |X| 만큼의 matching 을 가지게 된다. 

꿈과 현실의 차이는 $G'-G$ 만큼, 그것이 $d$ edges 다. 

남은 edge 들이 현실에서 만들 수 있는 maximum size of a matching 이다. <$|X| - d$>

그러니까 굳이 $d$를 만들어서 $G'$을 만들고... 이러는 이유는 단순히 "매칭이 가장 안된 케이스일 때, 그 때 나머지를 이어봐!" 라고 말하는 건 너무 엄밀하지 않으니, 엄밀한 갯수를 뽑아내기 위해 세운 증명용 장치다.

 

Definition.

Vertex cover: 모든 edge의 하나의 endpoint 라도 가진 set of vertices. edge 를 다 데려올 수 있는 vertex 모임.

$\beta(G)$: minimum size of a vertex cover. 최소 인원만 가지고 edge 다 데려오기.

 

Theorem (Konig-Egervary Theorem)

G 가 bipartite $\Leftrightarrow$ $\alpha'(G) = \beta(G)$

bipartite graph 에서 최대로 찾을 수 있는 짝의 갯수는 모든 edge 를 다 데려올 수 있는 최소 vertex 갯수.

$\textit{Proof}$

일단 vertex cover기만 하면 edge 들은 다 데려올 수 있으니까 $\beta(G) \geq \alpha'(G)$

그리고 앞에서 본 corollary 에 의해서 $\alpha'(G) = |X|-|T|+|N(T)|$ 인 subset T가 있다.

$N(T) \cup (X-T)$ 가 vertex cover 다.

이러면 $\beta(G) \geq |N(T)| + |X-T| = \alpha'(G)$,

vertex cover 가 최소 vertex cover 보다 큰데, 걔가 $\alpha'$인 셈.

$\alpha'$ 자체가 모든 "vertex를 다 포함할 수 있는" "matching (edge)" 의 set 인데, $\beta$ 는 그걸 "최소한" 으로 하려고 함.

 

Definition.

Edge cover: 모든 vertex 를 가진 set of edges. Vertex 다 데려올 수 있는 edge 모임.

$\beta'(G)$: minimum size of a edge cover. 최소 인원만 가지고 vertex 다 데려오기.

 

여기서 no isolated vertice 라는 가정을 해주고,

bipartite graph 에서

 

Lemma.

n-vertex graph G 에서

a vertex subset $S$ 는 independent set $Leftrightarrow$ $V(G) \backslash S$ 가 vertex cover.

그러니까 $\alpha(G) + \beta(G) = n$.

어떤 그룹을 뺴고 났더니 걔네가 vertex cover 라면, 걔들은 independent set 이다.

일단 $S$ 뺴고 나서도 edge 들은 싹 다 커버가 되는 상황이니, $S$ 들끼리 굳이 연결되어 있을 이유가 없다.

 

Theorem <Gallai>

G 가 n-vertex 이고, no isolated vertices $Rightarrow$ $\alpha'(G) + \beta'(G) = n$

최대한 뽑을 수 있는 match 갯수는 최소한으로 vertex를 커버하는 엣지의 갯수와 같다.

$\textit{Proof}$

$\beta'(G) \leq n-\alpha'(G)$ 먼저 보자면, $M$ 이라는 maximum matching 이 있다고 치자.

$M$에 못 낀 애들한테도 M에 낄 수 있게 edge 들을 추가해주면,

$M$ 밖에 있는 애들은 한 개의 edge를, $M$ 에 있는 애들은 총 M쌍의 vertex 들이 서로 짝을 짓고있다.

이러면 $n- 2|M| + |M|$ 이 되니까 $n-|M|$ 개가 커버되는 셈. 이렇게 하면 무조건 모든 vertex 들이 cover 되니까 minimum edge cover 보다 많은 수를 가진다.

그러므로 $\beta'(G) \leq n - \alpha'(G)$다. 

$\alpha'(G) \geq n- \beta'(G)$ 를 보자면, $L$ 이라는 smallest edge cover 가 있다고 치자

만약에 $L$에 있는 $e$ 이 endpoints 두개가 $L$에 있는 다른 친구랑 vertex가 겹친다면, $L-e$가 smaller edge cover니까 이럴 리는 없다.

그러니까 일단 $L$에 있는 애들은 degree가 많아봐야 1개 뿐이다. (2개 있으면 한명은 나가도 되니까). 그건 애들이 다 star 라는 뜻. 만약 $k$ 개의 star가 있다면, $|L| = n-k$ 개다. (star의 중심을 빼면 vertex 갯수 = edge 갯수니까).

각 star 에서 안겹치개 matching 을 찾는다는 건 하나의 edge를 선택하겠다는 거고, 총 $k$ 개의 edge가 나올테니까, $k = n-|L| = n-\beta'(G)$ 다.

그러니까 $\alpha'(G) \geq n- \beta'(G)$.

 

Fact.

이러면 bipartite graph 에서 $\alpha'(G) = \beta(G)$ 이고, $\alpha(G) = \beta'(G)$ 다.

 

4.2. Matchings in general graphs

Bipartite graph 의 경우를 일반적인 그래프에도 끌고 올 수 없다. 아주 간단히 $K+{2n+1}$ 만 봐도 그런데, $N(S)$ 가 $S$보다 바글바글 많음에도 불구하고 vertex 가 홀수여서 perfect matching 이 없기 떄문이다. 그런 의미에서 이 홀수 vertex의 요소들이 매우 중요하게 역할한다.

 

Definition.

k-factor: k-regular spanning subgraph of G. vertex는 싹 들어가고, edge 갯수가 모두 동일한 subgraph.

odd component: 홀수 order 의 component

$o(G)$: 그래프 G의 odd component 갯수

일단 odd component 는 "홀수~~~" 하고 모인 애들이니까, 걔들끼리 매칭해주려고 하다보면 꼭 한 명이 남는다.

어떤 그룹 $T \subseteq V(G)$ 라고 했을 때, $G-T$ 는 $o(G-T)$ 만큼의 odd component 를 가진다.

$T$ 를 빼고 남은 쩌리 그룹들 중 하필 홀수~~하고 모인 애들 그룹에서는 최소한 한명씩은 솔로가 나온다는 것.

그러니 $o(G-T) - |T|$ 는 진짜 아무리 뭘 어떻게 해도 발생하는 솔로 수이다. 이 수치는 매우 중요하다.

 

Theorem <Tutte's 1-factor>

$G$ 는 1-factor 를 가진다 $\Leftrightarrow$ $o(G-S) \leq |S|$ 이다.

$S$ 빼고 나머지 그룹들 중 홀수로 모인 그룹의 숫자가 $S$보다 작아야 매칭으로 구제해줄 수 있다.

 

Definition

Deficiency $def(S)$: $o(G-S) |S|$: 그래프 G에서 $S$ 를 뺀 부분집합에서 odd component 갯수에서 $|S|$를 뺌. 일단 $S$ 는 알아서 지들끼리 모이더라도 $S$뺀 나머지 그룹들 중 자체적으로 답을 못 내리는 $o(G-S)$ 중에서 $S$로 최대한 어떻게든 매칭 시켜주고도 답이 안나오는 애들.

 

Theorem <Berge-Tutte formula>

$\alpha'(G) = min_{S \subseteq V(G)} \frac{1}{2}(n-def(S))$

maximum 매칭 갯수는 진짜 답이 안나오는 애들 빼고, 나머지 애들로 짝 지어준 커플의 수다.

 

Lemma.

$o(G-S) - |S| \equiv n \pmod{s}$

총 애들 명 수랑, 인싸모임 $S$ 로 구제시켜주고도 남은 솔로애들은 같은 홀짝성을 가진다.

 

Lemma.

$T$가 maximum deficiency (답 안나오는 홀수모임 그룹이 최대, 너무 많아) 인 maximal set (그 와중에 얘는 제일 커) 이라고 치자.

$G-T$ 의 odd component $C$ 에 속한 vertex $u$가 있다면

$C-u$ $\Rightarrow$ Tutte's condition 을 만족한다.

$G-T$ 는 even component 가 없다.

가장 인싸 메이져스트림 무리인 $T$ 가 빠지고 난 쩌리 모임들은 그나마도 매칭 성공하는 짝수모임도 없다. 답도 안나오는 홀수 모임들 중에서 "한명만 빠지면" 그래도 매칭시켜줄 답이 나온다.

$\textit{Proof}$

인싸무리 $T$ 가 빠지고 남은 쩌리 그룹 $C$ 에서도, 그 와중에 인싸그룹 $S$ 를 찾을 수 있다.

$def_G(T \cup u \cup S) = o(G-T-u-s) - (|T} + 1 + |S|) = o(G-T) - 1- + o(C-u-S) - |T|-1-|S| = def_G(T)-2+def_{C-u}(S)$

일단 $C-u$ 가 짝수니까, $def_{C-u}(S)$ 도 짝수 by parity lemma.

그러니까 $def_G(T \cup u \cup S) \geq def_G(T)$ 이고 $S$가 positive deficiency 라면 이건 $T$의 선택에 위배. 그러니까 $C-u$ 는 음수의 deficiency 를 가진다 (구제가 가능하다). 그러니까 Tutte's condition 만족.

만약 $G-T$ 가 짝수 component 를 가진다면, T에다가 spanning tree 로 leaf 하나 추가하면 T랑 같은, 더 큰 set을 가지니까 이 경우는 고려 안함.

 

$textit{Proof of Berge-Tutte formula}$

Induction on $n$. 일단 $n>0$ 에 대해서, $C-u$ 들은 다 해결됐다! 이제 $T$ 에서 $G-T$ 로 뻗어나가는 edge 들을 가지고 matching 수를 뽑아내보자.

어떤 $Y$를 생각해보자. $G-T$ 로 뻗어나가는, $T$로부터 시작된 $|T|+d$ component 들을 가지는 set이다. T,Y-bigraph $H$ 를 생각했을 때, $H$ 는 edge ty $t \in T$, $y \in Y$ 인데, $G-T$의 어떤 vertex 가 $y$에 대응될 때에만 edge를 가질 떄 edge가 생기는 상황.

For $S \subseteq T$ 에서, $N_H(S)$가 아닌 $Y$ 의 모든 vertices 는 $G-(T-S)$ 의 odd component 를 이루고, $T$ 의 maximality 에 의해 $def(T-S) \leq d$ 다. 그러니까

$(|Y} - |N_H(S)|) - |T-S| \leq d$

이고, $|Y| = |T|+d$ 니까, 위 부등식은 $|S| \leq N_H(S)|$가 된다. Hall's theorem 으로 인해 $H$ 는 $T$를 cover 하는 matching 을 가지고, 이게 우리가 바라던 matching 이다.

 

Definition.

f-factor: spanning subgraph $H$, $d_H(v) = f(v) for all $v \in V(G)$. $f: V(G) \rightarrow \mathbf{N}_0$. 어떤 그래프 G의 subgraph 인데, 모든 vertex에 숫자를 부여하고 딱 그만큼으로 degree 갯수를 조정한 subgraph.

 

일단 $f(w) \leq d_G(w)$ 인건 가정해야하고, $e(w) = d_G(w) - f(w)$ , 그러니까 원래 degree 에서 f-factor에 쓰일 degree 를 뺸 만큼의 숫자를 표현하는 새로운 함수 excess degreee가 있다고 치자. 우리는 각 vertex 를 $K_{d(v),e(v)}$ 로 치환해서 새로운 그래프를 만들거다. 여기서 $d(v)$ 에 해당하는 부분을 $A(v)$, $e(v)$ 에 해당하는 부분을 $B(v)$라 하겠다.

Theorem

multigraph G 는 f-factor를 가진다 $\Leftrightarrow$ 위 변환을 거쳐 만든 그래프 $H$ 가 1-factor를 가진다.

k-factor 가"모든 vertex가 k개의 edge를 가질 때 perfect matching이 있음!!" 이라고 주장했으니,

"모든 vertex가 다른 edge를 가져도 perfect matching 이 있는 경우가 있음!!" 으로 일반화시킨 게 f-factor.

그 짓을 하려고 f와 degree 사이의 관계로 장난질을 쳐서 변환한 위 그래프를 사용.

$\textit{Proof}$

$\Rightarrow$ G가 f-factor 있으면, $A(v)$ 중에서 $e(v)$ 만큼의 edge 가 $B(v)$로 가서 닿으니까 perfect matching 있다.

$\Leftarrow$ H가 1-factor가 있으면, $B(v)$ 날리고, 거기에 해당하는 $A(v)$를 날리면 $f(v)$ 개의, degree 1짜리 vertex가 남는다.

 

Theorem <Tutte's f-factor theorem>

G가 f-factor를 가진다 $\Leftrightarrow$ $q(S, T) - \sum_{v \in T}d_{G-S}(v) \leq f(S) - f(T)$

for all disjoint subsets $S, T \subseteq V(G)$.

이 때, $f(S) = \sum_{v \in S} f(v)$ 이고, $q(S, T)$ 는 $G-(S \cup T)$ 중에서 $e_G(C, T) + f(V(C))$ 가 홀수가 되게 하는 component 의 갯수다.

메이져 인싸모임 $S, T$가 있다고 했을 때, 그 두 그룹에 못 낀 쩌리 그룹 중 $T$랑의 연결성을 고려해도 홀수인 그룹들을 $q(S, T)$ 라고 하고, $S$ 가 아닌 애들의 degree 합으로 구제해주는 그림.

 

Corollary <Petersen>

cut-edge가 없는 모든 3-regular 그래프는 1-factor다.

모든 edge가 사이클에 포함되어있는 3-regular graph 는 perfect matching 을 가진다.

$\textit{Proof}$

S가 maximum deficiency 를 가지는 set이라고 치자. $C$가 $S$에 못 낀 쩌리 odd component 다.

$\sum_{v \in C}d_G(v) = 3|C| = e_G(S, C) + 2e(C)$

C가 가지는, 또 C에서 뿜어져 나오는 모든 degree 의 합은 $3|C|$ 인데 (3-regular), 이게 몇개는 $S$랑 연결된 거고 몇 개는 $C$ 내부에서 노는 거일 거다.

그런데 $S$랑 $C$ 사이에 있는 edge 는 홀수개여야 맞는데, 또 cut-edge 는 없으니 1개는 아닐 거다. 그러니까 최소 3개임.

$3|S| \geq e_G(S, V(G) \backslash S) \geq 3o(G-S)$

이러면 처음이랑 마지막에 $|S| \geq o(G-S)$가 나오면서 Tutte's condition 나옴.