d라이브러리

“이번엔 제가 나설 차례군요. 선물을 빠르게 배달하려면 가장 좋은 이동 경로를 찾아야 하지요.” 뿔테 안경을 쓴 순록이 나섰어요. 한 번 갔던 길을 다시 가지 않고 모든 마을을 들를 수 있는 방법을 알려주겠대요. 

아래 보이는 그림은 ‘어수동 나라’의 지도예요. 마을 6개를 둘러싸고 강이 흐르고 있고, 각 마을을 잇는 다리나 길이 모두 11개 있지요. 어떻게 하면 11개의 길을 단 한 번씩만 지나면서 모든 길을 지나 처음 출발한 마을로 돌아올 수 있을까요? 

18세기의 스위스 수학자 레온하르트 오일러가 해결하고자 했던 문제도 바로 이거예요. 러시아 쾨니히스베르크라는 도시에서 머물던 그는 그곳에 있는 다리를 모두 한 번씩 건너 출발 장소로 돌아올 수 있는지 궁금해했지요. 그러다 좋은 생각이 떠올랐어요.

‘방문할 장소와 다리를 점과 선으로 바꿔 나타내면 어떨까?’

어수동 나라의 지도를 오일러가 생각한 방법대로 다시 그려볼까요? 마을을 점으로, 마을과 마을 사이를 잇는 다리나 길을 선으로 나타내면 왼쪽과 같은 모양으로 바뀔 거예요. 복잡했던 지도가 단순한 모양으로 바뀌니 문제도 한결 쉽게 풀 수 있게 됐어요. 펜을 떼지 않고 모든 점을 지나는 선을 그리면 되지요. 

그런데 이보다 더 복잡한 마을을 지날 땐 어떻게 할까요? 오일러는 직접 선을 따라 그려보지 않고도 간단하게 정답을 찾는 방법을 알아냈어요. 바로 각 점에 연결된 선이 2, 4, 6, 8…처럼 짝수 개인지 세어 보는 거예요. 만약 모든 점에 선이 짝수 개만큼 연결돼 있다면, 우리는 선을 한 번씩만 지나 처음 출발했던 점으로 돌아올 수 있지요.

오일러의 발견은 많은 수학자의 관심을 받았어요. 풀기 어려워 보이는 문제를 점과 선으로 단순하게 바꿔 금방 해결해주니까요. 이처럼 점과 선을 이용해 사물 사이의 관계를 알아내는 연구를 ‘그래프 이론’이라고도 부른답니다. 대도시의 복잡한 지하철 노선을 짤 때, 택배를 배달할 가장 빠른 방법을 찾을 때 아주 큰 역할을 하고 있지요.