1.planar graph
1부에서 우리는 지도를 그래프로 바꾸어 생각한다는 것을 알았습니다. 헷갈림을 방지하기 위해 몇 개의 그래프를 가지고 색칠연습을 해 봅시다.
첫번째. 이 그래프는 오른쪽의 지도에서 얻은 것입니다.(빵빵빵빵빵빵 님 오류제보로 수정(2015-12-27 02:23:22))
이렇게 칠할 수 있습니다.(빵빵빵빵빵빵 님 오류제보로 수정(2015-12-27 02:23:22))
두번째.
세번째. ..어?
세번째 그래프는 다섯개의 점이 모두 서로 연결되어 있으므로, 다섯개의 색이 필요합니다. 우리는 4색문제가 참임을 알고 그것을 증명하려고 하고 있는데, 반례를 찾아버린 것일까요?
지도를 그래프로 생각할 때 주의할 점이 하나 있는데, 모든 지도는 그래프로 바꿀 수 있지만, 모든 그래프를 지도로 바꿀 수 없다는 사실입니다. 위의 그래프가 좋은 예지요. 이 별모양 그래프와 일치하는 평면 위의 지도는 없습니다.
앞으로 생각하는 그래프들은 특별한 언급이 없는 한 모두 지도에서 나온 것으로 간주하므로, 평면 그래프 planar graph 로 생각합니다. 즉, 모든 그래프들은 평면 위에서 교차되지 않도록 그려집니다.
2.maximal planar graph
1부에서 우리는 4색문제를 증명하기 위해 귀류법을 사용한다고 했습니다. 그에 따라 4색문제의 반례가 존재합니다. 4색문제의 반례는 색칠하려면 다섯가지 이상의 색이 필요한 지도이죠.
반례 그래프. (물론 저건 반례가 아닙니다.. 반례 그래프를 진짜 그릴 수 있으면, 4색문제가 거짓임을 증명해버리는게 되잖아요. 위의 그림은 그냥 상징적인 그래프일 뿐입니다.)
그런데 반례가 다섯 가지 이상의 색이 필요하다는 사실만을 가지고는 문제를 풀기 힘들고, 조금 손을 대서 다듬어야 합니다. 첫번째 가공은 반례 그래프(이제부터는 지도말고 그래프만을 생각합니다.) 에 선을 추가하는 것입니다. 그래프에 선을 추가하면 어떤 일이 벌어질까요? 우리가 위에서 연습해본 것과 같이, 선으로 연결된 점들은 서로 다른 색으로 칠해야 합니다. 따라서 선이 추가되면, 원래의 그래프보다 좀 더 엄격하게 색을 칠해야 하죠. 이 때, 두 점사이의 선을 어떻게 추가하더라도, 원래 그래프보다 더 적은 색이 필요하게 될 수는 없다는 사실은 당연합니다. 따라서, 선을 계속 추가해도, 그건 계속 반례인 것이죠.
그렇게 선을 계속 추가해 나가면..
마치 3-D 모델의 폴리곤처럼.. 모든 면들은 삼각형이 되고, 더이상 선을 추가할 수 없는 지경에 이르게 됩니다.
더이상 선을 추가할 수 없는 상태. 이런걸 maximal planar graph라고 부릅니다.
3. 공식들
이 때 간단한 공식이 성립하게 됨을 알 수 있습니다. 각 선은 두 면과 맞닿아 있으므로, 모든 면 각각에 대해서 그 자신을 이루는 선을 세면, 모든 선을 두번 센것과 같죠. 그런데 위에서 봤듯이 모든 면이 삼각형이니까, 3f = 2e 가 됩니다. (여기서 f는 면의 갯수, e는 선의 갯수입니다.)
4색문제를 풀기 위해 두 개의 공식이 더 필요한데요, 하나는 위와 같은 원리로 알아낼 수 있는 공식입니다. 각 선은 양끝에서 두 점과 만나니까, 모든 점 각각에 대해서 그 자신과 만나는 선을 세면, 모든 선을 두 번 센것과 같죠. 점이 만나는 선의 갯수를 차수degree라고 합니다. 그러니까.. 각각의 점 vi의 차수를 di라고 한다면,
입니다.(이 공식은 평면 그래프 뿐만 아니라 모든 그래프에서 성립합니다)
시그마 기호가 익숙치 않은 분들을 위해 간단한 예를 보자면,
이 그래프에 있는 선의 개수는
이렇게 셀 수 있다 그말입니다.
이 공식은 악수정리 handshaking lemma 라고 부릅니다. 모임에서 모든 사람이 악수를 몇 번 했는지 알기 위해선, 각각의 사람들에게 자신이 몇 번 악수를 했는지 물어보면 되죠. 각 사람(점)들의 악수횟수(차수)를 다 더하면, 이건 모임에서 악수가 이뤄진 횟수(그래프의 선의 개수)의 두 배이죠. 악수라는건 두 명이 하는 거니까요.(그래프의 선의 양끝엔 점이 있으니까요)
나머지 하나는 오일러 정리입니다. 오일러가 만든 정리가 한두개가 아니라서 헷갈리는데.. 오일러의 다면체 정리는
"연결된 그래프가 있을 때, 점-선+면의 값은 항상 2이다"
라는 것입니다.
간단한 예. (다른 여러 그래프를 그려서 직접 그 값을 확인해 보세요!)
-증명-
사실 제대로 증명하려고 하면 골이 빠지는 정리인데.. 평면으로 한정하면 쉽게 증명할 수 있습니다.
모든 그래프는 점 하나만 있는 그래프에서 점과 선을 추가하여 얻을 수 있다. 점 하나만 있는 그래프의 경우 점은 한개, 선은 0개, 면은 한개이므로, 점-선+면 =1-0+1=2 이다.
점을 추가할 때.. 원래의 그래프와 연결하기 위해선 선이 하나가 추가된다. 점과 선이 하나씩 추가되면 점-선+면의 값은 변하지 않음을 알 수 있다.
선을 추가할 때.. 어떻게 선을 추가한다 하더라도 면이 하나 발생한다. 즉, 선과 면은 같이 추가된다. 이 때 역시 점-선+면의 값이 변하지 않음을 알 수 있다.
이상에서 항상 점-선+면 = 2 임을 확인하였다.////
( 이 증명은 귀납법을 이용한 증명을 바탕으로 쉽게 풀어쓴 거라 허점이 있을 수 있습니다만, 중대한 건 아닐 겁니다. )
자, 이제 하나의 중요한 결과를 알아내기 위한 준비가 완료되었습니다.
4. 결과
이 파트는 단순계산이므로, 수식을 보면 심장에 무리가 가는 분들은 그냥 넘기셔도 됩니다.
먼저 반례 그래프의 수치들을 기호를 붙여놓자. 점,선,면의 개수를 각각 n,e,f라 하고, 차수가 k인 점의 개수를 p_k라 하자. 그러면 3에서 알아본 것과 같이
n-e+f = 2 ..............(1)
2e = 3f ..................(2)
이다.
(1)에서 f=2-n+e이므로, 이것을 (2) 에 넣고 정리하면 3n-e=6 이 나온다. 양 변을 두 배를 하면
6n – 2e = 12
이다.
차수가 1인 점의 개수 + 차수가 2인 점의 개수 + ... 이렇게 전부 더하면 (당연히!) 모든 점의 개수인 n이 나온다. 즉,
이다.
한편, 악수정리에 의하여, 모든 차수를 다 더하면 2e이다. 즉, 1 x (차수 1인 점의 개수) + 2 x (차수 2인 점의 개수) + 3 x (차수 3인 점의 개수) + ....를 하면, 2e이다. 좀 더유식하게 표현하면,
이다.
이를 6n – 2e = 12 에 넣으면,
이고, 이를 정리하면 최종적으로
를 얻을 수 있다.
5. 그래서 그게 무슨 의미?
마지막에 튀어나온 식에서 중요한 사실은 별게 아닙니다. 시그마를 빼고 다시 써 보면
이죠. p_k들은 갯수이므로, 음수일 수가 없습니다. 그래서 –p_7, -2p_8 같은 건 전부 0이거나 음수항입니다. 그런데 우변은 양수니까, 좌변도 양수여야죠. 좌변이 양수이려면, 적어도 양수항 하나는 필요합니다. 즉, p_1,p_2,p_3,p_4,p_5 다섯 개 중 하나는 0은 아니어야 합니다.
우리는 앞에서 p_k들을 점들의 차수로 정의했으므로, 이 결과를 쉬운 말로 풀어 쓰면
“2의 과정을 거친 반례 그래프에는 반드시 차수가 5 이하인 점이 존재한다.”
가 됩니다.
이제 4색문제에서 중요한 국면 중 하나에 도달했습니다. 왜냐면 앞으로 다음과 같은 사실을 보이려고 할 거거든요.
“2의 과정을 거친 반례 그래프 중 어떤 것에는 차수가 5 이하인 점이 하나도 존재할 수 없다.”
이렇게 바라던 모순을 찾게 되는거죠. 이제 끝에 ‘이건 모순이다. 따라서 4색문제는 참이다.’ 라고 붙이기만 하면 증명은 완성됩니다!
..라고 하고 끝내면 참 좋겠지마는 현실은 그렇게 녹록치 않았습니다. 이건 100여년간 수학자들을 괴롭힌 문제고 이제 여러분들도 그 고통을 경험하시게 될 겁니다. ㅋ.ㅋ.
오늘은 여기까지.
창작글
글쓰기