쾨니히스베르크의 다리
종이에 그려 보면 압니다
종이에 점 네 개를 찍고 그 사이에 선 일곱 개를 그으세요. 이제 연필을 떼지 않고, 일곱 선을 하나도 빠뜨리지 않고, 하나도 두 번 지나지 않고 그려 보세요.
몇 번을 해도 마지막 한 선이 남습니다. 운이 나쁜 걸까요, 아니면 아예 안 되는 걸까요? 안 된다면, 그것을 어떻게 증명할까요?
이야기
Jakob Emanuel Handmann
Public domain · 위키미디어 공용
프로이센의 도시 쾨니히스베르크에는 강이 흐르고, 강에 섬이 둘 있고, 그것들을 잇는 다리가 일곱 있었습니다. 시민들 사이에 놀이 같은 물음이 돌았습니다 — 일곱 다리를 한 번씩만 건너 한 바퀴 돌 수 있을까?
아무도 못 했습니다. 그러나 「못 했다」와 「못 한다」는 다릅니다. 1736년, 레온하르트 오일러가 그 차이를 갈랐습니다.
그가 한 일은 놀랍도록 단순합니다. 땅을 점으로, 다리를 선으로 바꿨습니다. 섬이 얼마나 크든, 다리가 얼마나 길든 상관없습니다. 중요한 것은 무엇이 무엇과 몇 개로 이어져 있는가뿐입니다.
그렇게 보면 답이 저절로 나옵니다. 어떤 땅에 들어갔으면 나와야 합니다. 그러니 그 땅에 붙은 다리는 짝수여야 합니다. 시작한 곳과 끝나는 곳만 홀수일 수 있습니다. 그런데 쾨니히스베르크는 네 땅이 모두 홀수였습니다. 그래서 없습니다.
이 한 편의 글에서 그래프 이론이라는 수학이 태어났습니다.
지도 앱의 길 찾기가 여기서 나왔습니다. 「땅을 점으로, 다리를 선으로」 바꾼 그 순간이 그래프 이론의 시작이고, 지금 도로망·지하철 노선·통신망이 모두 이 그림으로 다뤄집니다.
쓰레기 수거차와 제설차의 경로, 우편 배달 순서도 이 문제의 후손입니다.
계단 넷 — 같은 사실을 네 깊이로
한붓그리기로 해 본다
다리를 선으로, 땅을 점으로 바꿔 그립니다. 강도 배도 지우고, 남는 것은 점 넷과 선 일곱뿐입니다.
이제 연필을 떼지 말고 그려 보세요. 안 됩니다. 선을 하나 지우고 다시 해 보세요. 이번엔 됩니다. 지웠을 때와 안 지웠을 때 무엇이 달라졌는지 눈으로 찾아보는 것이 오늘 할 일입니다.
홀수 땅이 몇 곳인가요
쾨니히스베르크는 네 곳이 다 홀수라 불가능했습니다.
홀수점 세기
점마다 거기 붙은 선이 몇 개인지 세어 적습니다. 쾨니히스베르크는 3, 3, 3, 5 — 넷 다 홀수입니다.
한붓그리기를 할 때 어떤 점을 지나간다는 것은 들어오는 선 하나와 나가는 선 하나를 짝지어 쓴다는 뜻입니다. 그러니 지나가기만 하는 점은 선이 짝수여야 합니다. 홀수인 점은 출발점이거나 도착점일 수밖에 없고, 그런 자리는 둘뿐입니다. 그런데 여기는 넷입니다. 그래서 안 됩니다.
다리를 놓아 보세요
실제로 1935년에 다리 하나가 더 놓여 지금은 가능합니다.
오일러 경로의 조건 증명
앞의 말을 정리하면 이렇습니다. 연결된 그림에서 한붓그리기가 되려면 홀수점이 0개이거나 2개여야 합니다. 0개면 출발한 자리로 돌아오고(닫힌 길), 2개면 한 홀수점에서 떠나 다른 홀수점에서 멈춥니다.
홀수점이 늘 짝수 개라는 것도 함께 보입니다. 선 하나가 양 끝에 1씩 보태니 모든 점의 수를 다 더하면 로 짝수이고, 짝수를 만들려면 홀수인 것이 짝수 개라야 하기 때문입니다. 그래서 홀수점이 1개나 3개인 그림은 아예 있을 수 없습니다.
차수의 합
그래서 합은 언제나 다리 수의 두 배 — 반드시 짝수입니다.
그래프 이론의 시작
오일러는 이 물음에 답하면서 길이도 각도도 쓰지 않았습니다. 쓴 것은 「무엇이 무엇에 붙어 있는가」뿐입니다. 그 눈이 그래프 이론이 되었고, 다시 위상수학으로 자랐습니다.
오늘날에는 모든 변을 한 번씩 지나는 길을 오일러 길, 모든 꼭짓점을 한 번씩 지나는 길을 해밀턴 길이라 부릅니다. 닮아 보이지만 앞의 것은 위 조건으로 바로 판정되고, 뒤의 것은 아직 빠른 판정법이 없습니다(NP-완전). 한 글자 차이가 이렇게 갈립니다.
여러 번 그으려면
이것이 우편배달 문제로 이어집니다.
풀어 보기
다리를 고쳐 놓기. 쾨니히스베르크의 네 땅을 라 하고, 붙은 다리 수가 차례로 3, 3, 3, 5 라 하자.
(1) 한붓그리기가 안 되는 까닭을 홀수점의 개수로 설명하시오.
(2) 다리를 하나만 새로 놓아 한붓그리기가 되게 하려 한다. 어느 두 땅을 이어야 하는지 모두 찾으시오.
(3) (2) 로 놓았을 때 출발점과 도착점이 어디인지 말하시오.
(4) 다리를 하나 없애서 되게 할 수도 있는가? 답과 까닭을 쓰시오.
(5) 출발한 자리로 돌아오려면 다리를 적어도 몇 개 놓아야 하는가?
(4) 가 함정입니다 — 없애도 됩니다. 양 끝 두 점이 함께 짝수로 바뀌니까요.
답과 풀이 보기
(1) 붙은 다리 수가 3, 3, 3, 5 — 넷 다 홀수입니다. 어떤 땅에 들어가면 나와야 하므로 다리는 짝을 이루어 쓰입니다. 홀수인 땅은 출발점이거나 도착점일 수밖에 없는데, 그런 자리는 많아야 둘입니다. 홀수점이 넷이니 한붓그리기는 불가능합니다.
(2) 새 다리 하나는 홀수점 둘을 이어야 합니다. 그 둘이 짝수로 바뀌어 홀수점이 둘만 남기 때문입니다. 넷 중 둘을 고르는 방법이므로 가지 — 모두 됩니다.
(3) 남은 홀수점 둘이 출발점과 도착점입니다. 예를 들어 를 이었다면 와 에서 출발해 서로에게 닿습니다.
(4) 됩니다. 이것이 이 문제의 함정입니다. 다리를 하나 없애면 그 양 끝 두 땅이 함께 짝수로 바뀌어 홀수점이 둘만 남습니다. 쾨니히스베르크의 일곱 다리는 모두 홀수점끼리 잇고 있으므로 어느 하나를 없애도 한붓그리기가 됩니다.
(5) 출발한 자리로 돌아오려면 홀수점이 하나도 없어야 합니다. 다리 한 개는 홀수점 둘을 없애므로, 넷을 없애려면 적어도 2개가 필요합니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「점과 선으로 바꿔 보기」는 오늘날 가장 널리 쓰이는 생각 가운데 하나입니다.
- 지하철 노선도 — 실제 거리와 모양을 버리고 이어진 관계만 남긴 그림입니다
- 내비게이션 — 길을 선으로, 교차로를 점으로 두고 가장 빠른 길을 찾습니다
- 우편·택배 경로 — 모든 길을 한 번씩 지나 돌아오는 가장 짧은 길을 찾는 문제가 이 물음의 자손입니다
- 친구 관계망 — 사람이 점, 아는 사이가 선입니다
이어지는 장
지도에서 크기와 각도를 모두 버리고 점과 선의 연결 관계만 남긴 오일러의 생각은, 입체 다면체의 꼭짓점·모서리·면을 세는 강력한 공식으로 뻗어 나갑니다 — 제59장에서 위상수학의 또 다른 결실을 확인해 보세요.
영감을 받은 곳
레온하르트 오일러가 1736년 상트페테르부르크 학술원에 제출하고 1741년 출간한 논문 「위치 기하학에 관한 문제의 풀이」에서 왔습니다.