지하철 노선도의 탄생-그래프이론

유한개의 정점과 변의 결합양식에 관한 이론을 뜻합니다.

 

가장 대표적인 것이 지하철 노선도. 노선도는 각 역과 철길을 점(●)과 선(-)으로만 나타내죠. 어느 역끼리 연결됐는지 간략하게 보여주지만 역과 역사이의 거리, 역의 정확한 위치 등 세세한 정보는 생략합니다.

 

이렇게 간단한데 무슨 이론이냐고요. 그래프이론이 하나의 연구 분야로 발돋움한 계기는 의외의 질문 덕분이라고 합니다. 1852년 영국의 수학자 오거스터스 드 모르간(Augustus De Morgan)은 자신의 수업을 듣던 학생으로부터 이런 질문을 받았습니다.

 

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

 

정답은 뭘까요? 일단 ‘아니다’임을 보이려면 모두 칠하는 데 5가지 색 이상이 필요한 지도를 1개만 찾으면 됩니다. 하지만 답이 ‘그렇다’라면 평면 지도란 지도는 전부 조사해야 해죠. 어떻게 답을 찾을까요? 간단해 보이지만 이문제는 무려 120년 넘게 수학자들을 골탕 먹였습니다.

 

1976년이 돼서야 미국의 수학자 케네스 아펠(Kenneth Appel), 독일의 수학자 볼프강 하켄(Wolfgang Haken)이 컴퓨터의 도움을 받아 4색 문제를 최초로 증명해냈죠. 문제가 처음 나오고 증명되기까지 124년이 걸린 셈입니다.

 

하지만 그 과정에서 나온 아이디어가 여러 그래프 색칠 문제에 활용되면서 그래프 이론이 발전했습니다.

 

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

 

그래프 이론은 지도 색칠하기 문제에서처럼 색채적으로 다양하게 응용될 수 있으며, 물리, 화학, 커뮤니케이션 과학, 컴퓨터 기술, 전기 및 토목 공학, 건축, 유전학, 심리학, 사회학, 경제학, 언어학 등 여러 분야에 영향을 끼치고 있습니다.

 

예를 들어, 역사적으로 중요한 업적으로 간주되는 생화학에서의 RNA 염기서열 분석에서도 그래프가 사용되었으며, 현재에도 유전학에서 유전자가 질병에 미치는 메커니즘을 밝히기 위하여 네트워크로 모델링하여 데이터를 분석하는 등 그래프 이론이 유용하게 쓰이고 있습니다.