이번에 더 배울 것
18세기 쾨니히스베르크에는 강 위의 두 섬과 양쪽 강변, 모두 네 땅덩어리를 잇는 다리 7개가 있었습니다. 시민들은 모든 다리를 정확히 한 번씩 건너는 산책이 가능한지 궁금해했습니다. 오일러는 땅덩어리를 노드로, 다리를 엣지로 바꾸었습니다. 같은 두 땅 사이에 다리가 두 개인 곳도 있어서 이 그래프는 다중 그래프입니다.
모든 엣지를 정확히 한 번씩 지나는 길을 오일러 경로(Eulerian path), 출발점으로 되돌아오는 경우를 오일러 회로(Eulerian circuit)라고 합니다. 길 중간에 들르는 노드는 들어온 만큼 나가야 하므로 엣지를 짝수 개씩 씁니다. 따라서 연결된 그래프에 오일러 회로가 있으려면 모든 노드의 차수가 짝수여야 하고, 오일러 경로가 있으려면 차수가 홀수인 노드가 0개 또는 2개(출발점과 도착점)여야 합니다. 이 조건이 충분하기도 하다는 증명은 훗날 히어홀처(Hierholzer)가 완성했습니다.
쾨니히스베르크는 한 섬에 다리 5개, 나머지 세 땅에 다리 3개씩이 닿아 네 노드의 차수가 모두 홀수입니다. 홀수 차수 노드가 4개이므로 그런 산책은 불가능합니다. 가능한 길을 하나하나 시도해 보지 않고 차수만 세어 ‘불가능’을 증명했다는 점이 이 풀이의 핵심입니다. 이 조건은 엣지를 한 번씩 지나는 문제에만 해당하며, 모든 노드를 한 번씩 방문하는 문제(해밀턴 경로)는 이렇게 간단한 판정법이 알려져 있지 않습니다.
작은 예제로 따라가기
쾨니히스베르크 그래프의 차수는 5, 3, 3, 3이고 합은 14=2×7(다리 7개)입니다. 홀수 차수 노드가 4개라 오일러 경로가 없습니다.
홀수 차수인 두 땅 사이에 다리를 하나 더 놓으면 그 두 노드의 차수가 짝수가 되어 홀수 차수 노드가 2개로 줄고, 남은 두 땅을 양 끝으로 하는 오일러 경로가 생깁니다.
동아리 네트워크는 차수 3인 노드가 6개라 오일러 경로가 없습니다. 지아–도윤, 서준–유나처럼 홀수 노드끼리 엣지 2개를 더해도 홀수 노드가 2개 남아 오일러 회로는 아직 불가능하고 경로까지만 생깁니다.
다리 하나를 더하거나 빼면
각 조건에서 홀수 차수 땅이 몇 곳이 되는지 먼저 세고, 모든 다리를 한 번씩 건너는 산책이 가능한지 예상하세요.
중간에 지나는 땅은 들어오고 나가는 다리가 짝을 이뤄야 하는데, 홀수인 땅이 넷이라 출발점과 도착점 두 곳으로는 다 감당할 수 없습니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.