<div>1부 : <span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><a target="_blank" href="http://todayhumor.com/?humorbest_1172542" target="_blank">http://todayhumor.com/?humorbest_1172542</a></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><span style="font-family:gulim, Dotum, Helvetica, AppleGothic, sans-serif;line-height:21.6px;font-size:9pt;"><br></span></div> <div><br></div> <div>1.planar graph</div> <div><br></div> <div>1부에서 우리는 지도를 그래프로 바꾸어 생각한다는 것을 알았습니다. 헷갈림을 방지하기 위해 몇 개의 그래프를 가지고 색칠연습을 해 봅시다.</div> <div><br></div> <div> <div style="text-align:left;"> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451180532rcWlahEvJextqbMbwS.png" width="798" height="221" alt="01.png" style="border:none;"></div><br></div></div> <div><br></div> <div>첫번째. 이 그래프는 오른쪽의 지도에서 얻은 것입니다.<font color="#7f7f7f">(빵빵빵빵빵빵 님 오류제보로 수정(2015-12-27 02:23:22))</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><br></div> <div> <div style="text-align:left;"> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451180536bhrLYwjh6aYb8Zf2gFdz5DF6wg.png" width="614" height="221" alt="02.png" style="border:none;"></div><br></div><br></div> <div>이렇게 칠할 수 있습니다<span style="font-size:9pt;line-height:1.5;">.</span><font color="#7f7f7f" style="font-size:9pt;line-height:1.5;">(빵빵빵빵빵빵 님 오류제보로 수정(2015-12-27 02:23:22))</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> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063253YdxFDUF4Dq.png" width="544" height="221" alt="03.png" style="border:none;"></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> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063258WWZwpliQgC9jWah2jafc.png" width="252" height="263" alt="04.png" style="border:none;"></div><br></div> <div>세번째. ..어?</div> <div><br></div> <div><br></div> <div>세번째 그래프는 다섯개의 점이 모두 서로 연결되어 있으므로, 다섯개의 색이 필요합니다. 우리는 4색문제가 참임을 알고 그것을 증명하려고 하고 있는데, 반례를 찾아버린 것일까요?</div> <div><br></div> <div>지도를 그래프로 생각할 때 주의할 점이 하나 있는데, <b>모든 지도는 그래프로 바꿀 수 있지만, 모든 그래프를 지도로 바꿀 수 없다</b>는 사실입니다. 위의 그래프가 좋은 예지요. 이 별모양 그래프와 일치하는 평면 위의 지도는 없습니다.</div> <div><br></div> <div>앞으로 생각하는 그래프들은 특별한 언급이 없는 한 모두 지도에서 나온 것으로 간주하므로, <b>평면 그래프 planar graph</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>2.maximal planar graph</div> <div><br></div> <div>1부에서 우리는 4색문제를 증명하기 위해 귀류법을 사용한다고 했습니다. 그에 따라 4색문제의 반례가 존재합니다. 4색문제의 반례는 색칠하려면 다섯가지 이상의 색이 필요한 지도이죠. </div> <div><br></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063277v9UFQxv3uaA.png" width="325" height="335" alt="05.png" style="border:none;"></div><br></div> <div><br></div> <div>반례 그래프. (물론 저건 반례가 아닙니다.. 반례 그래프를 진짜 그릴 수 있으면, 4색문제가 거짓임을 증명해버리는게 되잖아요. 위의 그림은 그냥 상징적인 그래프일 뿐입니다.)</div> <div><br></div> <div><br></div> <div>그런데 반례가 다섯 가지 이상의 색이 필요하다는 사실만을 가지고는 문제를 풀기 힘들고, 조금 손을 대서 다듬어야 합니다. 첫번째 가공은 반례 그래프(이제부터는 지도말고 그래프만을 생각합니다.) 에 선을 추가하는 것입니다. 그래프에 선을 추가하면 어떤 일이 벌어질까요? 우리가 위에서 연습해본 것과 같이, 선으로 연결된 점들은 서로 다른 색으로 칠해야 합니다. 따라서 선이 추가되면, 원래의 그래프보다 좀 더 엄격하게 색을 칠해야 하죠. 이 때, 두 점사이의 선을 어떻게 추가하더라도, 원래 그래프보다 더 적은 색이 필요하게 될 수는 없다는 사실은 당연합니다. 따라서, <b>선을 계속 추가해도, 그건 계속 반례</b>인 것이죠.</div> <div><br></div> <div>그렇게 선을 계속 추가해 나가면..</div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063283keAUEqhvECnVoNqWfuw4aI8If.png" width="375" height="231" alt="375px-Dolphin_triangle_mesh.png" style="border:none;"></div><br></div> <div><br></div> <div><br></div> <div>마치 3-D 모델의 폴리곤처럼.. 모든 면들은 삼각형이 되고, 더이상 선을 추가할 수 없는 지경에 이르게 됩니다.</div> <div><br></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063289OMbZXfB8LLsTDEJPq6b5FKHpbSrK9w.png" width="325" height="335" alt="06.png" style="border:none;"></div><br></div> <div><br></div> <div>더이상 선을 추가할 수 없는 상태. 이런걸 maximal planar graph라고 부릅니다. </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><br></div> <div>3. 공식들</div> <div><br></div> <div>이 때 간단한 공식이 성립하게 됨을 알 수 있습니다. 각 선은 두 면과 맞닿아 있으므로, 모든 면 각각에 대해서 그 자신을 이루는 선을 세면, 모든 선을 두번 센것과 같죠. 그런데 위에서 봤듯이 <b>모든 면이 삼각형</b>이니까, <span style="font-size:9pt;line-height:1.5;"><b><font color="#ff0000">3f = 2e</font></b> </span><span style="font-size:9pt;line-height:1.5;">가 됩니다. (여기서 f는 면의 갯수, e는 선의 갯수입니다.)</span></div> <div><br></div> <div><span style="font-size:9pt;line-height:1.5;">4색문제를 풀기 위해 두 개의 공식이 더 필요한데요, 하나는 위와 같은 원리로 알아낼 수 있는 공식입니다. 각 선은 양끝에서 두 점과 만나니까, 모든 점 각각에 대해서 그 자신과 만나는 선을 세면, 모든 선을 두 번 센것과 같죠. 점이 만나는 선의 갯수를 차수degree라고 합니다. 그러니까.. 각각의 점 vi의 차수를 di라고 한다면,</span></div> <div><br></div> <div> <div style="text-align:center;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063334mhmkfugIMJcYaBo52stnVp2.png" width="74" height="43" alt="11.png" style="border:none;"></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/1451063345QR4W8dkaSq.png" width="525" height="335" alt="08.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/1451063349fVb2u7tp3jaDpJ.png" width="741" height="555" alt="09.png" style="border:none;"></div><br></div> <div><br></div> <div>이렇게 셀 수 있다 그말입니다. </div> <div><br></div> <div>이 공식은  <b>악수정리 handshaking lemma</b> 라고 부릅니다. 모임에서 모든 사람이 악수를 몇 번 했는지 알기 위해선, 각각의 사람들에게 자신이 몇 번 악수를 했는지 물어보면 되죠. 각 사람(점)들의 악수횟수(차수)를 다 더하면, 이건 모임에서 악수가 이뤄진 횟수(그래프의 선의 개수)의 두 배이죠. 악수라는건 두 명이 하는 거니까요.(그래프의 선의 양끝엔 점이 있으니까요)</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>나머지 하나는 <b>오일러 정리</b>입니다. 오일러가 만든 정리가 한두개가 아니라서 헷갈리는데.. 오일러의 다면체 정리는 </div> <div><br></div> <div>"연결된 그래프가 있을 때, 점-선+면의 값은 항상 2이다"</div> <div><br></div> <div>라는 것입니다.</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063830yB5zfJtYnY.png" width="296" height="685" alt="17.png" style="border:none;"></div> <div style="text-align:left;">간단한 예. (다른 여러 그래프를 그려서 직접 그 값을 확인해 보세요!)</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> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div>-증명-</div> <div><br></div> <div>사실 제대로 증명하려고 하면 골이 빠지는 정리인데.. 평면으로 한정하면 쉽게 증명할 수 있습니다.</div> <div><br></div> <div><span style="font-size:9pt;line-height:1.5;">모든 그래프는 점 하나만 있는 그래프에서 점과 선을 추가하여 얻을 수 있다. 점 하나만 있는 그래프의 경우 점은 한개, 선은 0개, 면은 한개이므로, 점-선+면 =1-0+1=2 이다.</span></div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063902wdAvNaQwXHQ3enJcnUhb1nWni.png" width="296" height="208" alt="18.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>점을 추가할 때.. 원래의 그래프와 연결하기 위해선 선이 하나가 추가된다. <b>점과 선이 하나씩 추가되면 점-선+면의 값은 변하지 않음</b>을 알 수 있다.</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451064239e5VM7UMyUd.png" width="296" height="265" alt="19.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><br></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/1451064246oZehGT83epdnkxeVUQfdmnBRlXbmMwI.png" width="296" height="441" alt="20.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> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div><br></div> <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>( 이 증명은 귀납법을 이용한 증명을 바탕으로 쉽게 풀어쓴 거라 허점이 있을 수 있습니다만, 중대한 건 아닐 겁니다. )</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><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>4. 결과</div> <div><br></div> <div><font color="#7f7f7f">이 파트는 단순계산이므로, 수식을 보면 심장에 무리가 가는 분들은 그냥 넘기셔도 됩니다.</font></div> <div><br></div> <div><br></div> <div>먼저 반례 그래프의 수치들을 기호를 붙여놓자. 점,선,면의 개수를 각각 n,e,f라 하고, 차수가 k인 점의 개수를 p_k라 하자. 그러면 3에서 알아본 것과 같이</div> <div><br></div> <div>n-e+f = 2 ..............(1)</div> <div>2e = 3f ..................(2) </div> <div><br></div> <div>이다.</div> <div><br></div> <div>(1)에서 f=2-n+e이므로, 이것을 (2) 에 넣고 정리하면 3n-e=6 이 나온다. 양 변을 두 배를 하면</div> <div><br></div> <div>6n – 2e = 12 </div> <div><br></div> <div>이다.</div> <div><br></div> <div>차수가 1인 점의 개수 + 차수가 2인 점의 개수 + ... 이렇게 전부 더하면 (당연히!) 모든 점의 개수인 n이 나온다. 즉,<img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063414k5vQVJfb7jU1L.png" width="66" height="39" alt="12.png" style="font-size:9pt;line-height:1.5;border:none;"><span style="font-size:9pt;line-height:1.5;">이다.</span></div> <div><br></div> <div>한편, 악수정리에 의하여, 모든 차수를 다 더하면 2e이다. 즉, 1 x (차수 1인 점의 개수) + 2 x (차수 2인 점의 개수) + 3 x (차수 3인 점의 개수) + ....를 하면, 2e이다. 좀 더유식하게 표현하면,<img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063445tYGvfShrPymr.png" width="79" height="42" alt="13.png" style="font-size:9pt;line-height:1.5;border:none;">이다.</div> <div>이를 6n – 2e = 12 에 넣으면,</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063507vk3mXVkUMYvtS.png" width="136" height="39" alt="14.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/1451063512dgnDQwfl.png" width="118" height="41" alt="15.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><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>5. 그래서 그게 무슨 의미?</div> <div><br></div> <div>마지막에 튀어나온 식에서 중요한 사실은 별게 아닙니다. 시그마를 빼고 다시 써 보면</div> <div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201512/1451063520QM6dePuyJbVBDqXYJxrb.png" width="341" height="31" alt="16.png" style="border:none;"></div></div> <div><br></div> <div>이죠. p_k들은 갯수이므로, 음수일 수가 없습니다. 그래서 –p_7, -2p_8 같은 건 전부 0이거나 음수항입니다. 그런데 우변은 양수니까, 좌변도 양수여야죠. 좌변이 양수이려면, 적어도 양수항 하나는 필요합니다. 즉, p_1,p_2,p_3,p_4,p_5 다섯 개 중 하나는 0은 아니어야 합니다.</div> <div><br></div> <div>우리는 앞에서 p_k들을 점들의 차수로 정의했으므로, 이 결과를 쉬운 말로 풀어 쓰면</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><b><font size="3">“2의 과정을 거친 반례 그래프에는 반드시 차수가 5 이하인 점이 존재한다.”</font></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>가 됩니다.</div> <div><br></div> <div>이제 4색문제에서 중요한 국면 중 하나에 도달했습니다. 왜냐면 앞으로 다음과 같은 사실을 보이려고 할 거거든요.</div> <div><b><br></b></div> <div><b>“2의 과정을 거친 반례 그래프 중 어떤 것에는 차수가 5 이하인 점이 하나도 존재할 수 없다.”</b></div> <div><br></div> <div>이렇게 바라던 모순을 찾게 되는거죠. 이제 끝에<b> ‘이건 모순이다. 따라서 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><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>..라고 하고 끝내면 참 좋겠지마는 현실은 그렇게 녹록치 않았습니다. <span style="font-size:9pt;line-height:1.5;">이건 100여년간 수학자들을 괴롭힌 문제고 이제 여러분들도 그 고통을 경험하시게 될 겁니다. ㅋ.ㅋ.</span></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>오늘은 여기까지.</div>