The Dinitz problem은
n \\times n square를 색칠하는 것과 관련된 문제로,
5색 정리 등에서와 같이 색칠에 특정 조건이 주어진다: 같은 행이나 같은 열에 있는 cell은 색이 모두 달라야 한다는 것. 다른 점이 있다면, cell들이 사용할 수 있는 색의 범위가 각각의 cell에 대해 다르게 주어진다는 것이다. cell마다 모두 같게 주어진다면 라틴 방진의 존재성에 의해
n개의 색으로 색칠이 가능하다. Dinitz problem이 증명하고자 하는 것은 cell들이 사용할 수 있는 색의 범위가 각각의 cell에 대해 크기가
k인 색의 집합으로 주어질 때
(1), 색의 집합이 어떻게 주어져도 이웃한 cell의 색이 다른 색칠이 가능한
k의 최솟값은
n이라는 것이다.
n \\times n square의 각 cell에 크기 n인 색의 집합을 주자. 그러면 square는 같은 행이나 같은 열에 있는 cell의 색이 모두 다르도록 색칠가능하다.
이제부터 ‘색칠’을 ‘이웃한 꼭짓점의 색이 다른 색칠’이라는 의미로 사용하겠다.
Definition 그래프
G=(V,E)에 대하여 색의 집합
C\\ (|C|=k)가 주어졌을 때 각 꼭짓점이 C의 한 색으로 색칠 가능한
k의 최솟값을
\\chi(G)라 한다.
각
v \\in V에 대해 색의 집합
C(v)\\ (|C(v)|=k)가 어떻게 주어져도 각
v가
C(v)의 한 색으로 색칠 가능한
k의 최솟값을
\\chi_l(G)라 한다.
V’ \\subset V와
V’의 두 원소를 양끝점으로 가지는 변들의 집합
E’ \\subset E에 대하여
G’=(V’,E’)을 V’에 의해 induce된 부분그래프라고 한다.
Definition 유향그래프
(2) \\vec{G}=(V,E)와
v \\in V에 대하여
v를 시작점으로 가지는 변의 개수를
d^{+}(v)라 한다.
또한, 다음을 만족하는
V의 부분집합
K를
\\vec{G}의 kernel라고 한다.
1. K는 독립적이다(임의의 두 꼭짓점이 이웃하지 않다).
2. 임의의
u \\in V \\setminus K에 대하여
v \\in K가 존재하여
(u \\to v) \\in E이다.
유향그래프 \\vec{G}=(V,E)와 각 꼭짓점에 주어진 색의 집합 C(v)에 대하여
1. V의 임의의 원소 v에 대하여 |C(v)| \\geq d^{+}(v)+1가 성립한다.
2. \\vec{G}의 임의의 induce된 부분그래프의 kernel이 존재한다.
이면, G은 색칠가능하다.
|V|에 대한 귀납법을 사용한다.
\\cup_{v \\in V}C(v)의 한 원소 c를 잡고, V_c:={v \\in V \\mid c \\in C(v)}라 하자.
V_c에 의해 induce된 부분그래프는 가정에 의해 kernel K가 존재한다. 이제 V \\setminus K에 의해 induce된 부분그래프 G’를 생각하고, 각 v \\in V \\setminus K에 대해 C’(v)=C(v) \\setminus {c}를 주자.
G’의 꼭짓점의 개수는 |V|-|K| < |V|이며, 각 u \\in V \\setminus K에 대해
c \\in C(u) : |C’(u)| = |C(u)|-1 \\geq d_{\\text{before}}^{+}(u) \\geq d_{\\text{after}}^{+}(u) +1
c \\notin C(u) : |C’(u)|=|C(u)| \\geq d_{\\text{before}}^{+}(u)+1 \\geq d_{\\text{after}}^{+}(u)+1
이고K가 V_c에 의해 induced된 부분그래프의 kernel이므로 c \\in C(u)인 경우 u \\in V_c에서 v \\in K가 존재하여 (u \\to v) \\in E인데 G’에서는 이 u \\to v들이 제거되므로 d^{+}(u)가 감소하여 d_{\\text{before}}^{+}(u) \\geq d_{\\text{after}}^{+}(u) +1이 된다. c \\notin C(u)일 경우 d^{+}(u)는 감소하거나 일정하므로 d_{\\text{before}}^{+}(u)+1 \\geq d_{\\text{after}}^{+}(u)+1이다.),
\\vec{G}의 임의의 induce된 부분그래프의 kernel이 존재함에서 \\vec{G’}의 임의의 induce된 부분그래프의 kernel 또한 존재하므로 G’은 조건을 모두 만족한다. 따라서 귀납가설에 의해 G’의 색칠이 존재한다. 이제 이 색칠에 c로 색칠된 K의 원소들과 제거했던 변들을 추가하면 G의 색칠이 완성된다. 따라서 증명이 끝났다.
2.3. Stable Matching ✎ ⊖
Definition 이분그래프
G=(U \\cup V, E)에서
matching M \\subset E은 임의의 두 원소도 공통된 끝점을 가지지 않는 변의 집합을 말한다.
U의 각 원소
u에 대하여
u와 이웃한 꼭짓점들의 순위
N(u,v_i)와
V의 각 원소
v에 대하여
v와 이웃한 꼭짓점들의 순위
N(v,u_i)가 정의되어있다고 하자. 예를 들어,
u와 연결된 두 꼭짓점
v_1, v_2에 대하여
N(u,v_1)>N(u,v_2)임은
u가
v_1보다
v_2를 더 선호함을 뜻한다. 이 때, 임의의
(u-v) \\in E \\setminus M에 대하여
(u-v’) \\in M,\\ N(u,v)<N(u,v’)인
v’ 또는
(u’-v) \\in M,\\ N(v,u)<N(v,u’)인
u’이 존재하는, 즉 ‘
u-v라는 짝이 새로 생성되어 손잡고 달아나지 않을’
M \\subset E를
G의
stable matching이라고 한다.
Stable matching을 찾는 방법에는 Gale-Shapley Algorithm이 있다. 이는 다음과 같이 구성된다.
(3)1.
R \\subset U를 연결된 변이 존재하는
U의 원소의 집합으로 정의한다.
2.
R의 짝이 없는 원소들이 연결되어있는
V의 고백해보지 않은 원소들 중 우선순위가 가장 높은 원소에게 다같이 고백한다. 고백받은
V의 원소들은 (있다면) 현재 자신의 짝과 자신에게 고백한
U의 원소들 중 우선순위가 가장 높은 원소를 선택하여 자신의 짝으로 하고 나머지를 찬다.
3. 현재 짝이 없는
R의 원소들 중 자신의 마지막 우선순위에 있는 원소에게 아직 고백을 해보지 않은 원소들로
R을 다시 구성한다.
4.
|R|=0이라면 알고리즘을 종료하고, 공집합이 아니라면 2로 돌아가 반복한다.
임의의 이분그래프 G=(U \\cup V, E)의 stable matching이 존재한다.
Proof Gale-Shapley Algorithm의 타당성을 증명하면 된다.
짝을 찾지 못한 R의 원소들은 매 턴마다 고백하는 V의 원소의 우선순위가 낮아지므로 언젠가 자신의 마지막 우선순위에 있는 원소에게 고백을 하게 되고, 결국 짝을 찾지 못했다면 R에서 나가게 된다. 즉 |R|은 언젠가 0이 되며, 이 알고리즘은 종료된다.
알고리즘이 종료됬을 때 어떤 (u-v) \\in E \\setminus M을 보자. 만약 u가 v에게 고백을 해보지 않았다면 u는 우선순위가 높은 원소에게 먼저 고백을 하므로 v보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 (u-v’) \\in M,\\ N(u,v)<N(u,v’)인 v’가 존재한다. 그리고 u가 v에게 고백을 해보았다면 v가 u를 찬 것이므로 u보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 (u’-v) \\in M,\\ N(v,u)<N(v,u’)인 u’가 존재한다. 그러므로 알고리즘의 결과물은 stable matching이다.
n \\times n square의 각 cell에 크기
n인 색의 집합을 주자. 그러면 square는 같은 행이나 같은 열에 있는 cell은 색이 모두 다르도록 색칠가능하다.
Proof n \\times n 라틴 방진을 하나 그리고, 각 cell을 점에 대응시키자. 같은 행에 있는 두 cell에 대하여 숫자가 작은 cell을 시작점으로, 숫자가 큰 cell을 끝점으로 하는 유향변을 그리고, 같은 열에 있는 두 cell에 대하여 숫자가 큰 cell을 시작점으로, 숫자가 작은 cell을 끝점으로 하는 유향변을 그리자. 이렇게 유향그래프
\\vec{S_n}=(V,E)을 구성할 수 있다.
임의의
v \\in V에 대하여
d^{+}(v)=n-1이므로
|C(v)| \\geq d^{+}(v)+1가 만족된다. 따라서
\\vec{S_n}의 임의의 induce된 부분그래프의 kernel이 존재함을 증명하면 보조정리 1에 의해 증명이 끝난다.
\\vec{S_n}에서 행의 집합을
R, 열의 집합을
L라 하자. 그리고
V’ \\subset V에 대하여
r \\in R과
l \\in L이
v \\in V’에서 겹칠 때
r-l을 그리는 방식으로 그래프
G=(R \\cup L, V’)를 구성하자.
(4) 그러면
G는 이분그래프가 된다. 이제 각 꼭짓점(이 꼭짓점은
\\vec{S_n}의 꼭짓점과는 분명히 다르다.
G는 행과 열을 꼭짓점으로 갖는 그래프이다)과 연결된 꼭짓점들의 우선순위를 겹치는 꼭짓점(이 꼭짓점은
\\vec{S_n}의 꼭짓점이다)의 연결상태로 결정하자. 즉 유향변(이 유향변은
\\vec{S_n}의 유향변이다)의 시작점을 포함하는 꼭짓점의 우선순위가 끝점을 포함하는 우선순위보다 낮도록 설정하자.
그러면 보조정리 2에 의해
G의 stable matching
K \\subset V’가 존재한다.
V’에 의해 induce된
\\vec{S_n}의 부분그래프
\\vec{S’_n}=(V’,E’)에서
K는 독립적이며
(5), 임의의
u \\in V’ \\setminus K에 대하여
v \\in K가 존재하여
(u \\to v) \\in E’이다.
(6) 즉 정의에 의해
K는
V’의 kernel이다.
따라서
\\vec{S_n}의 임의의 induce된 부분그래프의 kernel이 존재함을 증명했고, square는 같은 행이나 같은 열에 있는 cell은 색이 모두 다르도록 색칠가능하다.
