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