<div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;font-size:9pt;line-height:21.6px;"><a target="_blank" href="http://todayhumor.com/?science_56135">http://todayhumor.com/?science_56135</a>   1부</span></div> <div><br></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;"><a target="_blank" href="http://todayhumor.com/?science_56261">http://todayhumor.com/?science_56261</a>   2부上</span></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>시작하기 전에 : 이제부터 추가되는 많은 용어들은 영어 그대로 사용핧 것입니다. 제가 4색문제에 사용된 영어 용어들의 한글번역을 모르기 때문이기도 한데, 그보다는.. 직접 예를 들어 보지요. 뒤에 가면 이런 종류의 논의가 튀어나올 겁니다.</div> <div><br></div> <div>“....그들이 발견한 graph configuration들의 집합의 unavoidability는 discharging procedure를 통해서 증명할 수 있다. ”</div> <div><br></div> <div>이걸 한글로 바꾼다면 (번역된 용어를 모르기 때문에 직접 번역했습니다.)</div> <div><br></div> <div>“.... 그들이 발견한 그래프 형상들의 배제불가능성은 방전 절차를 통해서 증명할 수 있다.”</div> <div><br></div> <div>한글로 읽힌다는 사실 외에는 이해하는데 도움이 되지 않음을 느끼실 수 있을 겁니다. 왜냐면 이것들은 우리가 일상에서 쓰는 단어의 그 의미로써 쓰이고 있지 않거든요. 대체 ‘배제불가능성’ 이 뭘까요? 이건 누군가가 정의해놓은 뜻을 보기 전까지는, 추측만 할 수 있을 뿐 알 수 없습니다. 저는 앞으로 이런 새 용어들을 전부 설명할 겁니다. 그런데 단어 뜻을 전부 설명한다면,  그 단어가 영어이냐 한글이냐는 별 상관이 없겠지요. “~~ 한 상태를 A라고 한다.” 랑, “~~한 상태를 갑이라고 한다.” 랑의 차이를 보세요.</div> <div><br></div> <div>자. 그러면 지금의 상황을 이해해주시리라 믿고.. 계속 진행해 봅시다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>지난화에서 최대 평면 그래프 maximal planar graph 인 4색문제의 반례는 반드시 차수 5 이하인 점을 갖는다는 것을 알아냈습니다. 그때 말했던 것처럼, 이것과 모순되는 사실을 찾아내려고 합니다. 이와 모순을 찾아내기 위해서는 간단하게 위의 명제의 부정을 생각해보면 됩니다. </div> <div><br></div> <div>주어진 명제는</div> <div><br></div> <div>“최대평면 그래프 maximal planar graph 인 반례에는 반드시 차수degree가 5 이하인 점이 존재한다.”</div> <div><br></div> <div>이므로, 이것의 부정은</div> <div><br></div> <div>“<b>어떤</b> maximal planra인 반례에는 차수가 5 이하인 점이 하나도 없다.” </div> <div><br></div> <div>가 되죠. 이제 그게 “<b>어떤</b>‘ 그래프인지를 찾아보면 됩니다. </div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>1. minimal counterexample</div> <div><br></div> <div><span style="font-size:9pt;line-height:1.5;">그래프를 파는 쇼핑몰이 있다고 합시다. 4색문제의 반례를 찾으면, 앞에서 알아본 것과 같이 반드시 하나 이상이 검색되겠죠?</span></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491245fQFlseYhy4waeo7coQ.png" width="511" height="472" alt="1.png" style="border:none;"></div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>검색결과를 점갯수 오름차순 정렬을 합니다. </div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491252PxyIjbIUZBu5ywRTt.png" width="511" height="472" alt="2.png" style="border:none;"></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491256dFYZ2nuLJoLG9wFjNuZxxbf4idqbYve6.png" width="511" height="376" alt="3.png" style="border:none;"></div><br></div> <div><br></div> <div>그러면 점갯수가 제일 작은 것부터 검색결과에 나올 겁니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>이렇게 <b>점갯수가 제일 작은</b> 걸 이제부터 최소반례 minimal counterexample 라고 합시다. minimal counterexample의 특징은 그 정의에서 볼 수 있듯이 .. 그것들이 제일 작다는 사실입니다. 제일 작다는게 무슨 말이냐면, 이것들에서 점을 하나만 빼 본다면, 더이상 반례가 아니라는 말입니다. 그건 당연하죠. 방금 우리가 최저가 최저 점갯수인 것을 선택했으니까, 그것보다 작은 반례는 없을 테니까요. </div> <div><br></div> <div>이렇게 점갯수가 최소인 것들 중에 maximal planar 인 반례는 반드시 있습니다. 이건 당연하죠. 점갯수가 최소인 반례에서 선을 있는대로 집어넣으면 그게 maximal planar graph니까요. 그리고 이게 우리가 앞으로 관심갖게 될 녀석입니다.</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491269jmhU1hd5jjyfvPoqQp3mD.png" width="325" height="335" alt="4.png" style="border:none;"></div><br></div> <div>maximal planar graph인 minimal counterexample.(아까 그 검색에 나온 첫번째 그래프.)</div> <div><br></div> <div>자. 이제, <b>“ 차수가 1,2,3,4 인 점이 하나도 없”는 녀석</b>을 찾아냈습니다. </div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>1.a 이녀석이 차수3인 점을 안 가지는 이유</div> <div><br></div> <div>귀류법으로 알아낼 수 있습니다. 차수 3인 점이 있다고 칩시다. </div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491288q2B3GljGdx15.png" width="244" height="234" alt="5a.png" style="border:none;"></div><br></div> <div><br></div> <div>당연히 선의 끝에는 서로 다른 점들이 있겠죠.</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491292RmlYJH3VIihB4TPDfBGkZ2ny1i.png" width="244" height="234" alt="5b.png" style="border:none;"></div><br></div> <div><br></div> <div>그리고 이 점들은 서로 연결되어 있겠지요. (우리가 현재 다루고 있는 반레는 maximal planar입니다. 만약 이 점들이 직접 연결되어 있지 않다면, 선을 더 그을수가 있어요.즉 maximal planar가 아니게 돼요.)</div> <div><br></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491298e56wx7Eorcfm4AjRD3s81.png" width="244" height="234" alt="5c.png" style="border:none;"></div><br></div> <div><br></div> <div><br></div> <div>가운데 점을 하나 뺍니다. minimal counterexample이었으므로, 이렇게 빼면 더이상 반례까 아닙니다. 즉, 네 가지 색으로 칠할 수 있습니다. </div> <div><br></div> <div>물론 우리가 지금 이 바깥의 모양을 알고 있는건 아닙니다. 그러나 너무 당연한 이유로 지금 그림에 있는 세 점은 칠할 수 있습니다.</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491304Njez9eORXctHmXV.png" width="244" height="234" alt="5e.png" style="border:none;"></div><br></div> <div>삼각형의 꼭지점들은 서로 연결되어 있으니까요. 서로 다른 색으로 칠해질 수밖에 없습니다.</div> <div><span style="font-size:9pt;line-height:1.5;"><br></span></div> <div><span style="font-size:9pt;line-height:1.5;">그런데, 이건 말이 안됩니다. 아까 뺀 점을 다시 추가해보세요. 그러면 그래프는 아까의 반례가 되지만</span></div> <div><br></div> <div><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491316hnPhmvvW1yo4so58ZujiYWXkCNLfV.png" width="244" height="234" alt="5f.png" style="border:none;"></div> <div><br></div> <div>삼각형 꼭지점 위에서 쓰이지 않은 네 번째 색을 여기에 칠하면..</div> <div><br></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491348SIP9xp87oAqLBMkmyeVa2VrWOULTln1.png" width="244" height="234" alt="5g.png" style="border:none;"></div><br></div> <div><br></div> <div>자. 이제 4가지 색만으로 반례를 칠했습니다. 이건 불가능하죠. 반례의 정의가 4가지 색으로 못 칠하는 그래프니까요. 귀류법에 의하여, 여기에 차수 3인 점은 없습니다. ///</div> <div><br></div> <div>완전히 같은 방법으로 차수 1.2 인 점도 없음을 보일 수 있습니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>1.b. 이녀석이 차수 4인 점을 안 가지는 이유</div> <div><br></div> <div>차수 4일 때는 더이상 위의 테크닉을 사용할 수 없습니다. 왜냐면 각 꼭지점에 모두 다른 색이 칠해지면, 4가지 색을 다 써버리잖아요. </div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491356cjIzrtlo3pcZvVDU8.png" width="244" height="234" alt="6a.png" style="border:none;"></div><br></div> <div><br></div> <div>가운데 점을 빼서 나머지 부분을 4색으로 다 칠하고. 점을 다시 추가했을 때, 다섯번째 색이 필요할 수도 있죠. 물론, 사각형의 꼭지점을 두가지 색이나 세가지 색만으로 색칠된다면 또 모를까. 음..좀 헷갈리네요. 차근차근 써 보도록 합시다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>차수 4인 점이 있다고 하자. 앞의 과정과 똑같이 가운데 점을 빼면, 4색으로 그래프를 색칠할 수 있다.</div> <div><br></div> <div>case 1. 만약, 가운데 점을 뺀 그래프를 4가지 색으로 색칠했을 때, 사각형의 꼭지점 네 개가 오직 두 가지 색만으로 칠해진다면</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491365E8hZ3YY61Xthxj.png" width="244" height="234" alt="6b.png" style="border:none;"></div><br></div> <div><br></div> <div>즉 이런 경우, 다시 점을 추가해도 색의 추가 없이 가운데 점을 색칠할 수 있으므로,(파란색이나 초록색을 칠하면 되죠.) 앞의 삼각형일 때와 같은 이유로 모순이다. 따라서 이 케이스가 일어나는건 불가능하다.</div> <div><br></div> <div> <div style="text-align:left;"><br></div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>case 2. 사각형의 꼭지점이 세 가지 색으로 칠해진다면</div> <div><br></div> <div><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491373pDeGTHIlV4eI3CVFm8RWBkfPC.png" width="244" height="234" alt="6c.png" style="border:none;"></div> <div><br></div> <div>이때도 역시 다시 점을 추가해도 색이 추가되지 않으므로, 이 케이스도 불가능하다.</div> <div><br></div> <div>마지막 case 3. 사각형의 꼭지점이 모두 다른 색으로 칠해진다면</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491388zsulrmETnQJY7Ff9VCQwDmuhPHoo4pA.png" width="244" height="234" alt="6d.png" style="border:none;"></div><br></div> <div><br></div> <div>자. 이 부분이 재미있는 부분인데, 이것의 해결방법은 (우리가 지금 하고 있는 이 과정을 처음 발견한 Alfred Kempe의 이름을 딴) <b>Kempe chain</b> 을 이용합니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div> Kempe chain이란 색칠된 그래프 위에서 특정한 두 색이 번갈아가며 반복되는 고리를 말합니다. 이 역시 그냥 예를 보는게 이해가 빠른데..</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491395D8LjIz4QzDfF7gYRjPORhDy1ezS8.png" width="244" height="234" alt="7.png" style="border:none;"></div><br></div> <div><br></div> <div>이 그래프를 살펴보면, 파랑-노랑 Kempe chain은</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491400ZKxLPLp2KR37.png" width="244" height="234" alt="7b.png" style="border:none;"></div><br></div> <div><br></div> <div>이렇게 한개가 있고, 빨강-노랑 Kempe chain은</div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491404qkWEPCsaMgicGY7oF.png" width="244" height="234" alt="7c.png" style="border:none;"></div><br></div> <div>이렇게 2개가 있음을 알 수 있습니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>원래 문제로 돌아와서... 사각형의 꼭지점마다 다른 색이 칠해져 있을 때.. 마주 보는 두 꼭지점이 가지고 있는 두 색을 선택합시다. </div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491429zg5u8gbFzBTlyOUtthKo1H6Z.png" width="244" height="234" alt="6d.png" style="border:none;"></div><br></div> <div><span style="font-size:9pt;line-height:1.5;">즉 여기서 빨강-노랑을 선택하거나, 파랑-초록을 선택합니다. 우리는 빨강-노랑을 선택해 봅시다. 빨강과 노랑에서부터 시작하여, 빨강-노랑 Kempe chain을 <b>최대한으로</b> 연장해 봅시다.</span></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>subcase 3-1. </div> <div><br></div> <div>만약 chain이 연결되지 않는다면, 이런 식으로 그려지겠지요.</div> <div><br></div> <div><img src="http://thimg.todayhumor.co.kr/upfile/201512/14514914142rlbiJ4W.png" width="498" height="260" alt="8.png" style="border:none;"></div> <div><br></div> <div><b>이들 주변의 모든 점은 파랑과 초록으로만 이루어져 있습니다. 따라서 빨강과 노랑의 색을 서로 맞바꾸어도, 마주하는 나라가 같은 색을 가지게 될 일은 없습니다.</b></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491443xXjMFr1wQKoqTk5J6yjf.png" width="498" height="668" alt="8b.png" style="border:none;"></div><br></div> <div><br></div> <div>이렇게 한 쪽의 chain의 색을 뒤바꾸면, 어떤가요? <b>사각형 위에는 단 3개의 색만이 놓이게 됩니다</b>. 이 상태로 다시 가운데에 점을 추가하고, 사용하지 않은 색 (이 경우에는 빨간색) 을 추가하면, 4가지 색으로 반례를 칠해버린 게 되죠. 이건 모순이니 이 케이스도 불가능합니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>마지막 subcase 3-2. </div> <div><br></div> <div>chain이 연결된다면, 앞에서와 같이 빨강-노랑의 색을 뒤바꿔도 사각형 위에는 여전히 4가지 색이 놓이게 됩니다. </div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/14514914518SzPCNdco7oGV55X.png" width="498" height="266" alt="8c.png" style="border:none;"></div><br></div> <div><br></div> <div>그런데 이런 상황이라면, <b>파랑-초록 Kempe chain은 연결될수가 없</b>죠. 빨강-노랑 Kempe chain이 둘 사이를 갈라놓고 있으니까요.</div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491458oKU1STShMApK583HXq5ucrHNu45.png" width="498" height="300" alt="8d.png" style="border:none;"></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div><br></div> <div><br></div> <div>따라서 이번에는 파랑-초록 Kempe chain의 관점에서, 한쪽 chain의 색을 뒤바꿀 수 있습니다.</div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/14514914666f25UyKE.png" width="498" height="300" alt="8e.png" style="border:none;"></div><br></div> <div><br></div> <div>그러면 이번에도 사각형 위에 단 3개의 색만이 놓이게 되고, 위와 같은 원리로 모순이 발생합니다.</div> <div><br></div> <div>자. 이상에서 모든 케이스가 불가능함을 보였으므로, 귀류법에 의하여 maxinal planar graph인 minimal counterexample에는 차수 4인 점을 가지지 않습니다.////////</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>지금까지 우리가 해온걸 정리해봅시다.</div> <div><br></div> <div>먼저, 우리가 2부上에서 발견한 사실</div> <div><br></div> <div>“maximal planar graph 인 반례에는 반드시 차수 5 이하인 점이 존재한다.”</div> <div><br></div> <div>이 성립함과 동시에,</div> <div><br></div> <div>“maximal planar graph 인 반례 중 어떤 것(minimal counterexample) 에는 절대로 차수 1,2,3,4 인 점이 존재할 수 없다.”</div> <div><br></div> <div>도 성립함을 알았습니다.</div> <div><br></div> <div>이제, 다음을 보일 수 있다면..</div> <div><br></div> <div><b><font color="#ff0000">“maximal planar 이면서 minimal counterexample인 어떤 그래프는 차수 1.2.3.4점은 커녕 차수 5인 것도 없다.”</font></b></div> <div><br></div> <div>그렇다면, 이건 우리가 2부上에서 발견한 것과 모순이죠. 그러면 증명은 끝납니다. 이것이 Kempe가 보이려고 했던 것이고.. 실제로 그는 보였습니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><font color="#ff0000"><b>(라고 그는 생각했습니다.)</b></font></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>얼마 지나 그의 증명에서 결함이 발견되었죠. 그는 <b>차수5인 점을 제거하는데 실패</b>했던 것입니다. </div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>2. 이제 어떡하죠</div> <div><br></div> <div>우리가 아는 사실을 좀 다른 식으로 표현해 봅시다. 앞으로 반례라고 말하면, 편의상 maximal planar 이면서 minimal 인 것을 지칭하는 것으로 합시다.</div> <div><br></div> <div>“반례에는 반드시 있어야 하는 점이 있다. (차수 1,2,3,4 또는 5인 점)”</div> <div><br></div> <div>“반례에는 반드시 없어야 하는 점도 있다. (차수 1,2,3그리고 4인 점)”</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>혹은 이렇게 표현해 봅시다.</div> <div><br></div> <div>“반례를 어떻게 만들어도 피할 수 없는 형태가 있다. 어떤 반례에도 아래의 형태 중 하나는 있어야 한다..”</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491486OaK9fQ9whULaNjQE3IZCU3V.png" width="449" height="105" alt="9.png" style="border:none;"></div><br></div> <div><br></div> <div>우리가 앞에서 보았듯이 차수 3인 점의 주변 모양은 하나로 결정됩니다. 그래서 “점”에 대해 말하지 않고 이렇게 더 큰 “형태”에 대해서 말해도 돼요.</div> <div><br></div> <div>“반례에는 절대로 존재할 수 없는 형태도 있다. 어떤 반례에도 아래의 형태가 있다면, (우리가 앞에서 한 과정과 비슷한 방법으로) 4가지색만으로 그 그래프를 칠할 수 있게 된다. 아래와 같은 리스트를 가지면 그런 일이 일어난다..”</div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491491mFD6DKWhgIkZBH4vuaDx8XnpKQJbE.png" width="362" height="105" alt="10.png" style="border:none;"></div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>Appel과 Haken의 4색문제 풀이는 위의 명제에서 그림 부분만 바꾼 것과 다를바가 없습니다. 그들의 4색문제 첫 증명은 이런 식입니다.</div> <div><br></div> <div><br></div> <div><b><font color="#ff0000">4색문제가 거짓이라고 가정하자. 그러면 반례가 존재한다.</font></b></div> <div><b><font color="#ff0000"><br></font></b></div> <div><b><font color="#ff0000">반례를 어떻게 만들어도 피할 수 없는 형태가 있다.그것은 아래와 같다.</font></b></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491506KHuJso66.png" width="362" height="494" alt="11.png" style="border:none;"></div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451491509Asr7haWZ3AXwFcY.png" width="362" height="494" alt="12.png" style="border:none;"></div> <div style="text-align:left;"><br></div> <div style="text-align:left;">.</div> <div style="text-align:left;">.</div> <div style="text-align:left;">.....</div> <div style="text-align:left;">.</div> <div style="text-align:left;">.</div> <div style="text-align:left;">...</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">(이렇게 1936개)</div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div><br></div> <div><br></div> <div><font color="#ff0000"><b>반례에는 절대로 존재할 수 없는 형태도 있다. 그건 위에 그려진 것과 같다.</b></font></div> <div><font color="#ff0000"><b><br></b></font></div> <div><font color="#ff0000"><b>이건 모순이다. 따라서 4색 정리는 참이다.Q.E.D.</b></font></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>자. .. 이제 여러분은 이해하실 수 있습니다. 문제를 유한한 케이스로 나누어 컴퓨터에 집어넣었다는 것이 무엇인지를 말이죠. 그리고 그와 동시에 더 많은 질문이 생기실 겁니다. </div> <div><br></div> <div><br></div> <div><br></div> <div>그 질문들에 대한 대답은 다음 시간에.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>참고 : 1.a끝부분에서 차수 1,2인 점을 제외하는데 사실 이 점들은 어려운 과정 없이 지도에서 만들어지는 그래프의 특징에 의해 즉시 케이스에서 제외됩니다. 서술의 복잡함을 피하기 위해서 그냥 차수 3인 경우와 같은 방법으로 풀었습니다.  </div> <div><br></div> <div>subcase 3-2에서 암묵적으로 사용된 정리가 있는데, Jordan curve theorem입니다. Jordan curve theorem의 내용은 말하기에 어이가 없는데.. “평면에서 고리의 안과 밖은 분리되어 있다.” 거든요. 직관적으로 당연하지만 증명하기는 끔찍합니다. 우린 그냥 사용합시다.</div>