본문 바로가기주요메뉴 바로가기

주메뉴

IBS Conferences

[완독 도전! 수학시리즈 ③] 그래프 이론

  • ※ 편집자 주 : 기초과학연구원(IBS)은 물리, 화학, 생명과학, 지구과학, 융합 그리고 수학이라는 6개 분야에서 세계적 수준의 기초연구를 수행하고 있습니다. 새해를 맞이해 올해는 그간 도전하지 못했던 IBS의 수학분야 연구를 소개하기 위해 [완독 도전] 시리즈를 발행했습니다. 1편 오쿤코프 바디, 2편 유리균질공간에 이어 3편 그래프 이론으로 [완독 도전] 시리즈를 마칩니다. 많은 관심에 감사드립니다. IBS 드림.

대학에서 수학을 전공한 필자이지만 기초과학연구원(IBS) 연구자들의 논문에 나온 오쿤코프 바디며, 유리균질공간은 너무나 생소하게 느껴졌다. 그러다 수학시리즈의 마지막 주제가 '그래프 이론'이라는 말을 들었을 때 조금 안도했다. 적어도 '그래프'는 알고 있으니까.

하지만 그래프 이론에서 말하는 그래프는 학창시절 내내 배운, 좌표공간에 함숫값을 나타낸 그것이 아니라 오직 점과 선으로만 이뤄진 그림을 말한다. 그래프 이론은 수학과 전혀 상관없는 질문에 답하는 과정에서 발전한 독특한 연구 분야다. 2018년 12월 새로 출범한 IBS 수리 및 계산과학 연구단은 그래프로 세상의 문제들에 답을 내기 시작했다. 이를 설명하기 위해 먼저 그래프 이론이 무엇인지부터 소개하려 한다.

여러 가지 그래프. (엄상일 제공)
▲ 여러 가지 그래프. (엄상일 제공)

▣ 도움 : 엄상일 IBS 수리 및 계산과학 연구단, 이산수학 그룹 CI
▣ 참고 : 하켄이 들려주는 4색 정리 이야기(차용욱, 자음과모음)

지하철 노선도가 그래프라고?

지하철 어플리케이션(앱)에서 볼 수 있는 지하철 노선도는 그래프의 한 예다. 노선도라는 그래프에서 역은 점(●)으로, 철길은 선(-)으로 나타낸다. 어느 역끼리 연결됐는지 간략하게 보여주지만 역과 역사이의 거리, 역의 정확한 위치 등 세세한 정보는 생략한다. 덕분에 서울 경기권에 있는 정류장 수백 개를 모두 알지 못해도 이 노선도만 있다면 어디든 갈 수 있다.

지하철 노선도는 역의 연결 상태를 점과 선으로 보여주는 그래프다. (출처: 서울도시철도)
▲ 지하철 노선도는 역의 연결 상태를 점과 선으로 보여주는 그래프다. (출처: 서울도시철도)

그래프의 특징을 기억하면 평면 지도를 그래프로 바꿔 나타낼 수도 있다. 경계선으로 둘러싸인 도시를 한 점으로 나타내고, 경계선을 공유하는 두 도시는 선으로 연결하면 된다. 변을 끊거나 꼭짓점을 없애지 않고, 꼭짓점의 위치를 바꾸거나 변을 늘이고 줄여서 같은 그림이 되는 그래프는 모두 같은 그래프로 본다.

평면 지도에서 얻은 그래프. 출처: Inductiveload
▲ 평면 지도에서 얻은 그래프. 출처: Inductiveload

색칠 놀이에서 시작된 그래프 난제

그래프 이론이 하나의 연구 분야로 발돋움한 계기는 의외의 질문에서부터였다. 1852년 영국의 수학자 오거스터스 드 모르간(Augustus De Morgan)은 자신의 수업을 듣던 학생으로부터 질문을 하나 받았다.

'영국의 행정구역을 하나씩 색칠하되 경계선이 맞닿는 것끼리는 서로 다른 색으로 칠했더니 4가지 색으로 모든 구역을 칠할 수 있었습니다. 그렇다면 평면 위에 그린 모든 지도는 이처럼 4가지 색으로 색칠할 수 있을까요?'

이 질문의 답이 '아니다'임을 보이려면 모두 칠하는 데 5가지 색 이상이 필요한 지도를 1개만 찾으면 된다. 하지만 답이 '그렇다'라면 평면 지도란 지도는 전부 조사해야 했다. 어떻게 지도를 분류할 것인가를 보이기 위해 수많은 수학자가 고심했다. 하지만 이 문제가 120년 넘게 풀리지 못할 거라 생각한 사람은 없었다.

나라의 개수, 인접한 형태에 상관없이 어떤 지도든 4색이면 충분할까? (출처: Fibonacci)
▲ 나라의 개수, 인접한 형태에 상관없이 어떤 지도든 4색이면 충분할까? (출처: Fibonacci)

드 모르간의 전략은 간단했다. 먼저 n가지 색으로 칠할 수 있는 지도만의 특징을 생각해냈다.

'n가지 색으로 색칠 가능한 지도에는 반드시 어떤 n개 나라가 존재하는데, 이 n개 나라는 다른 n-1개 나라와 인접한다는 것이 특징이다. 예를 들어, 4가지 색으로 색칠 가능한 지도에는 4개 나라(A, B, C, D)가 반드시 존재하며 A는 B, C, D와 인접하고, B는 A, C, D와, C는 A, B, D와, D는 A, B, C와 인접한다.'

이런 논리로 1색으로 색칠 가능한 지도, 2색으로 색칠 가능한 지도…의 집합을 만들고, 다음과 같이 생각했다.

'색칠하는 데 5색 이상이 필요한 지도는 원래 평면 위에 그릴 수 없는 지도임을 증명하면, 모든 평면지도는 4색으로 칠할 수 있는 지도임을 자동 증명하게 된다!'

하지만 드 모르간의 논리에는 처음부터 허점이 있었다. 논리에 따르면 4색으로 색칠 가능한 지도는 모두 다른 3개 나라와 동시에 인접하는 4개 나라를 포함하고 있어야 하지만, 그렇지 않고도 4색으로 색칠 가능한 지도가 있었기 때문이다.

왼쪽 지도와 달리 오른쪽 지도는 모두 다른 3개 나라와 동시에 인접하는 4개 나라를 갖지 않지만 4색으로 색칠 가능하다.
▲ 왼쪽 지도와 달리 오른쪽 지도는 모두 다른 3개 나라와 동시에 인접하는 4개 나라를 갖지 않지만 4색으로 색칠 가능하다.

4색 문제 푼 아이디어들

4색 문제를 푸는 데에는 '최소 반례(Minimal counterexample)'와 '다섯 이웃 정리(Only five neighbor theorem)'라는 두 아이디어가 중요했다.

최소 반례

만약 4색만으로는 인접한 나라를 다른 색으로 칠하기가 어려운 지도가 여럿 있다면, 그 지도들 가운데 가장 적은 수의 나라를 가진 지도를 찾을 수 있다. 이 지도를 최소 반례라고 한다. 즉, 최소 반례보다 나라의 개수가 적은 모든 지도는 4색만으로 충분히 색칠할 수 있다.

다섯 이웃 정리

모든 평면 지도에는 인접한 나라가 기껏해야 5개 이하인 나라가 반드시 1개 이상 있다. 이 정리에 따르면 어떤 평면 지도라도 그 안에는 1개 나라와 인접한 나라(1각 나라)부터 5개 나라와 인접한 나라(5각 나라)까지, 다섯 가지 중 최소 1개는 있다.

이 아이디어들을 통해 최소 반례도 평면 지도이므로 여기에도 다섯 이웃 정리가 성립할 것이며, 1각 나라부터 5각 나라까지 다섯 가지 중 한 가지 형태를 반드시 갖고 있다고 말할 수 있다. 1879년 영국의 수학자 알프레드 켐페(Alfred Kempe)는 1각 나라부터 5각 나라까지 각각이 최소 반례 안에 있다고 가정할 경우 모순이 생긴다는 결론을 이끌어냄으로써 최소 반례라는 건 처음부터 존재할 수 없고, 그러므로 모든 평면 지도는 4색 이하의 색으로 모두 칠할 수 있음을 증명했다…라고 알려졌다. 단 11년 동안만!

히우드가 든 반례. 4색으로 칠할 수 있는 지도이지만, 위와 같이 칠하면 마치 5색이 필요한 지도로 보인다. 출처: Percy Heawood
▲ 히우드가 든 반례. 4색으로 칠할 수 있는 지도이지만, 위와 같이 칠하면 마치 5색이 필요한 지도로 보인다. 출처: Percy Heawood

11년 뒤인 1890년, 영국 수학자 퍼시 히우드(Percy Heawood)가 켐페의 증명 방식으로는 생각할 수 없는 지도의 예를 찾아내면서 4색 문제는 다시 미해결 상태가 됐다. 1976년, 지금까지 밝혀진 사실을 토대로 미국의 수학자 케네스 아펠(Kenneth Appel), 독일의 수학자 볼프강 하켄(Wolfgang Haken)이 컴퓨터의 도움을 받아 4색 문제를 최초로 증명해냈다. 문제가 처음 나오고 증명되기까지 124년이 걸린 셈이다.

하지만 그 과정에서 나온 아이디어가 여러 그래프 색칠 문제에 활용되면서 그래프 이론이 발전했다. 최근에도 수학자들은 하트비거(Hadwiger)의 추측, 텃(Tutte)의 4-flow 추측 등 4색 문제의 확장 문제를 계속해서 연구하고 있다.

한붓그리기에서 출발한 최신 그래프 연구

4색 문제가 그래프 이론을 발전시켰다면, 쾨니히스베르크의 다리를 배경으로 한 한붓그리기 문제는 그래프 이론 연구의 시초라고 할 수 있다. 18세기 프로이센의 쾨니히스베르크시는 강을 따라 다리가 7개 있는 독특한 지형이었다. 이곳을 방문한 누군가가 '어디서부터 시작하든 모든 다리를 한 번씩 건너서 제자리로 돌아올 수 있을까?'라고 물었는데, 스위스의 수학자 레온하르트 오일러(Leonhard Euler)가 그럴 방법이 없다는 것과 그래프가 연결돼 있으면서 각 꼭짓점에 연결된 변이 모두 짝수 개여야 한붓그리기를 할 수 있다는 점을 증명했다.

쾨니히스베르크의 지형을 나타낸 그래프. (출처: Leonhard Euler)
▲ 쾨니히스베르크의 지형을 나타낸 그래프. (출처: Leonhard Euler)

한붓그리기가 되는 그래프라면 그래프를 사이클(cycle)로 분할할 수 있다는 것을 쉽게 알 수 있다. 사이클은 시작점과 끝점이 같은 길 중에서도 같은 변을 2번 이상 지나지 않는 경우를 말한다.

그렇다면 언제 그래프를 길이가 짝수인(변이 짝수 개인) 사이클로 분할할 수 있을까? 이것도 그래프를 연구하는 수학자들의 연구 주제 중 하나다. 폴 세이무어(Paul Seymour) 미국 프린스턴대 수학과 교수가 1981년에 이와 관련해 만든 정리는 대략 이런 내용이다.

'이중 연결(2-connected)됐으면서 고리(loop)가 없고, 전체 변의 개수와 각 점에 연결된 변의 개수가 짝수인 평면 그래프는 변이 짝수 개인 사이클로 분할할 수 있다'

그래프 이미지

왼쪽 그래프는 이중 연결되지 않고, 고리도 있는 그래프다. 어느 두 꼭짓점을 잡아도 그 사이에 서로 같은 꼭짓점을 겹치게 사용하지 않는 경로가 2개 이상 있으면 이중 연결된 그래프라고 한다. 왼쪽 그래프에서는 가운데에 있는 한 점 때문에 왼쪽에 있는 점에서 오른쪽에 있는 점으로 가는 경로는 모두 가운데 점을 지날 수밖에 없어서 이중 연결되지 않았다. 고리는 그래프의 왼쪽 상단처럼 한 점에서 나와 한 점으로 들어가는, 변 1개로 이뤄진 사이클을 말한다.

반면, 오른쪽 그래프는 세이무어 교수의 정리 속 조건을 모두 만족하기 때문에 변이 4개인 사이클 2개로 분할할 수 있는 그래프다.

엄상일 CI와 폴 세이무어 교수. (엄상일 제공)
▲ 엄상일 CI와 폴 세이무어 교수. (엄상일 제공)

작년 12월, IBS 수리 및 계산과학 연구단 이산수학그룹 CI(Chief Investigator)로 부임한 엄상일 KAIST 수리과학과 교수는 토니 후인(Tony Huynh), 마리암 베르디안-리지(Maryam Verdian-Rizi) KAIST 박사후 연구원과 함께 변이 짝수 개인 사이클로 분할할 수 있는 그래프의 조건을 조금 달리해서 새로운 사실을 증명했다.

'이중 연결됐고 고리가 없으면서 각 꼭짓점에 연결된 변의 수는 짝수인 그래프 중에서 odd K4 마이너가 없는 그래프는 변이 짝수 개인 경우에 똑같이 변이 짝수 개인 사이클로 분할할 수 있다.'

세이무어 교수의 정리와 비교했을 때 차이는 '평면'그래프라는 조건이 빠지고, 'odd K4 minor가 없는' 그래프라는 조건이 추가됐다는 점이다. 여기서 K4는 꼭짓점이 4개이면서 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 완전 그래프를, minor(마이너)는 어떤 그래프에서 변이나 꼭짓점을 지우거나 변을 축약해서 만들 수 있는 그래프를 뜻한다.

왼쪽의 완전 그래프 <i>K<sub>5</sub></i>는 오른쪽 그래프의 마이너다.

Odd K4 마이너는 이런 것이다. 처음에 각 변에 1을 모두 쓰자. 이제는 축약할 때 0인 변만 축약할 수 있다. 그런데 꼭짓점 하나를 잡고 그 꼭짓점을 다른 꼭짓점과 잇는 모든 변에서 1을 0으로, 0을 1로 바꾸는 연산이 허용된다. 이런 식으로 축약하거나 변이나 꼭짓점을 지워서 모든 변이 1인 K4가 나오면 그 그래프가 odd K4 마이너를 갖는다고 한다.

엄 CI의 증명은 변을 축약해도 odd K4 그래프를 만들 수 없는 그래프에 관한 것이다. 이후 이 증명에 대한 반례가 나와 odd K4 마이너 그래프가 없는 조건만 가지고는 '평면 그래프 중에 모든 꼭짓점과 다 만나는 면이 있는 경우'에 한해 변이 짝수 개인 사이클로 분할할 수 있음이 밝혀졌다.

엄 CI는 "원래 이 연구의 시작은 odd K5 마이너가 없는 경우에도 되는지 궁금해서였다"면서 "그 이유는 평면 그래프는 K5 마이너가 없기 때문에, 만일 odd K5 마이너가 없는 경우에도 같은 것이 된다면(길이가 짝수인 사이클로 분할할 수 있다면) 세이무어 교수의 정리를 포함하게 되기 때문"이라고 말했다. 하지만 odd K5 마이너가 없는데도 짝수 길이의 사이클로 분할할 수 없는 예를 캐나다 워털루대의 허철원 학생이 찾았다.

그래프 분할을 포함한 그래프 이론의 여러 문제는 효율적인 일정 짜기, 통신 오류를 줄이기 위한 좋은 부호 체계 만들기 등 여러 분야에 활용되고 있다. 퀴즈로 시작한 작은 물음은 흥미로운 수학 연구로 발전하고, 세상을 바꾸기도 한다.

본 콘텐츠는 IBS 공식 블로그에 게재되며, https://blog.naver.com 에서 확인하실 수 있습니다.

게시판 이전 및 다음 링크
이전
만족도조사

이 페이지에서 제공하는 정보에 대하여 만족하십니까?

콘텐츠담당자
커뮤니케이션팀 : 백서윤   042-878-8238
최종수정일 2019-01-30 19:14