The Dinitz Problem (편집) (8)

(편집 필터 규칙)

=== 본 증명 ===
[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]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.