[호평동 수학학원] 오일러, 다리 일곱 개 산책 문제에서 시작된 수학

18세기 유럽에 쾨니히스베르크라는 도시가 있었습니다. 지금은 러시아 땅이 되어 칼리닌그라드라는 이름으로 불리는 곳입니다. 이 도시에는 강이 흐르고 있었고, 강 가운데 섬 두 개가 있었으며, 이 섬들과 강 양쪽 육지를 잇는 다리가 모두 일곱 개 있었다고 전해집니다. 당시 이 도시 사람들 사이에서는 이런 궁금증이 돌았다고 합니다.

일곱 개 다리를 모두 한 번씩만 건너서, 처음 출발한 곳으로 되돌아오는 산책 경로가 있을까 하는 것이었습니다. 여러 사람이 실제로 걸어보며 시도했지만 아무도 성공하지 못했다는 이야기가 전해집니다. 이 문제가 수학자 레온하르트 오일러의 귀에 들어갔습니다. 오일러는 직접 걸어보는 대신 전혀 다른 방식으로 문제에 접근했습니다.

다리의 정확한 길이나 섬의 모양, 강의 폭 같은 것은 이 문제에서 전혀 중요하지 않다는 사실을 알아챈 것입니다. 중요한 것은 오직 하나, 각 땅덩어리가 몇 개의 다리와 연결되어 있는가 하는 점이었습니다. 그래서 오일러는 육지와 섬을 점 네 개로, 다리를 그 점들을 잇는 선 일곱 개로 단순화했습니다.

지도를 완전히 다른 그림으로 바꿔버린 것입니다. 이렇게 단순화하고 나면 문제는 이렇게 바뀝니다. 점과 선으로 이루어진 이 그림을, 선 하나하나를 딱 한 번씩만 지나면서 펜을 떼지 않고 그릴 수 있는가. 오일러는 여기서 한 가지 규칙을 발견했습니다. 한 점에 선이 몇 개 모여 있는지를 세어보면, 그 점을 지나갈 때마다 들어오는 선 하나와 나가는 선 하나가 짝을 이루어 사용된다는 것입니다.

즉 출발점과 도착점이 아닌 이상, 어떤 점을 거쳐 가려면 그 점에 연결된 선의 개수는 짝수여야 합니다. 들어왔다가 나가는 일이 반복되기 때문입니다. 쾨니히스베르크의 네 땅덩어리에 연결된 다리 수를 세어보면, 한 곳은 다리 5개, 나머지 세 곳은 각각 3개씩 연결되어 있었다고 합니다.

다시 말해 네 점 모두 홀수 개의 선을 가지고 있었던 것입니다. 그런데 방금 살펴본 규칙에 따르면, 출발점과 도착점을 제외한 나머지 점들은 반드시 짝수 개의 선을 가져야 합니다. 만약 출발점으로 돌아오는 산책, 즉 시작점과 끝점이 같은 경우라면 모든 점이 짝수 개의 선을 가져야 한다는 결론이 나옵니다.

네 점이 전부 홀수였던 쾨니히스베르크에서는 이 조건을 도저히 만족시킬 수 없었던 것입니다. 그러니 사람들이 아무리 애써도 성공하지 못했던 것은 우연이 아니라 애초에 불가능한 경로를 찾고 있었기 때문이었습니다. 오일러는 이 결과를 1735년 무렵 논문으로 정리해 발표했다고 알려져 있습니다.

이 논문이 특별한 이유는 답 하나를 구했다는 데 있지 않습니다. 다리를 건너는 구체적인 산책 문제를 점과 선의 관계, 즉 연결 구조의 문제로 바꾸어 생각했다는 점이 새로웠던 것입니다. 이런 사고방식은 훗날 그래프 이론이라는 수학의 한 분야로 자라났습니다. 오늘날 지하철 노선도를 단순한 점과 선으로 그리는 것, 인터넷 연결망을 분석하는 것, 배달 경로를 최적화하는 것까지 모두 이 사고방식의 연장선에 있습니다.

이 이야기가 흥미로운 지점은 오일러가 대단히 복잡한 계산을 한 것이 아니라는 데 있습니다. 오히려 그는 필요 없는 정보를 과감히 지우고 문제의 뼈대만 남기는 방법을 택했습니다. 다리의 길이도, 섬의 크기도, 강물의 흐름도 다 지우고 나니 점 네 개와 선 일곱 개, 그리고 홀수와 짝수라는 아주 단순한 개념만 남았습니다.

복잡해 보이는 문제일수록 무엇을 남기고 무엇을 지울지 판단하는 것이 수학에서 중요한 힘이 된다는 것을, 이 오래된 다리 이야기가 잘 보여줍니다.