(+)분류 : 가져온 문서/오메가
The Dinitz problem은 n \\times n square를 색칠하는 것과 관련된 문제로, 5색 정리 등에서와 같이 색칠에 특정 조건이 주어진다: 같은 행이나 같은 열에 있는 cell은 색이 모두 달라야 한다는 것. 다른 점이 있다면, cell들이 사용할 수 있는 색의 범위가 각각의 cell에 대해 다르게 주어진다는 것이다. cell마다 모두 같게 주어진다면 라틴 방진의 존재성에 의해 n개의 색으로 색칠이 가능하다. Dinitz problem이 증명하고자 하는 것은 cell들이 사용할 수 있는 색의 범위가 각각의 cell에 대해 크기가 k인 색의 집합으로 주어질 때(1), 색의 집합이 어떻게 주어져도 이웃한 cell의 색이 다른 색칠이 가능한 k의 최솟값은 n이라는 것이다.
1. 서술 ✎ ⊖
n \\times n square의 각 cell에 크기 n인 색의 집합을 주자. 그러면 square는 같은 행이나 같은 열에 있는 cell의 색이 모두 다르도록 색칠가능하다.
2. 증명 ✎ ⊖
이제부터 ‘색칠’을 ‘이웃한 꼭짓점의 색이 다른 색칠’이라는 의미로 사용하겠다.
2.1. 용어의 정의 ✎ ⊖
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이다.
각 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이다.
2.2. 보조정리 1 ✎ ⊖
유향그래프 \\vec{G}=(V,E)와 각 꼭짓점에 주어진 색의 집합 C(v)에 대하여
1. V의 임의의 원소 v에 대하여 |C(v)| \\geq d^{+}(v)+1가 성립한다.
2. \\vec{G}의 임의의 induce된 부분그래프의 kernel이 존재한다.
이면, G은 색칠가능하다.
1. V의 임의의 원소 v에 대하여 |C(v)| \\geq d^{+}(v)+1가 성립한다.
2. \\vec{G}의 임의의 induce된 부분그래프의 kernel이 존재한다.
이면, G은 색칠가능하다.
2.2.1. 증명 ✎ ⊖
|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의 색칠이 완성된다. 따라서 증명이 끝났다.
\\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로 돌아가 반복한다.
Stable matching을 찾는 방법에는 Gale-Shapley Algorithm이 있다. 이는 다음과 같이 구성된다.(3)
1. R \\subset U를 연결된 변이 존재하는 U의 원소의 집합으로 정의한다.
2. R의 짝이 없는 원소들이 연결되어있는 V의 고백해보지 않은 원소들 중 우선순위가 가장 높은 원소에게 다같이 고백한다. 고백받은 V의 원소들은 (있다면) 현재 자신의 짝과 자신에게 고백한 U의 원소들 중 우선순위가 가장 높은 원소를 선택하여 자신의 짝으로 하고 나머지를 찬다.
3. 현재 짝이 없는 R의 원소들 중 자신의 마지막 우선순위에 있는 원소에게 아직 고백을 해보지 않은 원소들로 R을 다시 구성한다.
4. |R|=0이라면 알고리즘을 종료하고, 공집합이 아니라면 2로 돌아가 반복한다.
2.4. 보조정리 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이다.
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이다.
2.5. 본 증명 ✎ ⊖
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은 색이 모두 다르도록 색칠가능하다.
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은 색이 모두 다르도록 색칠가능하다.
