퍼레이드 – 쾨니히스베르크의 2~7번 다리
이 지도는 쾨니히스베르크를 보여주고 있으며, 도시를 가로지르는 강과 강 한가운데의 섬, 그리고 강을 가로지르는 일곱 개의 다리가 표시되어 있습니다. 쾨니히스베르크 사람들은 모든 다리를 한 번씩 건너는 퍼레이드를 하고 싶어 했습니다. 하지만 일곱 개의 다리를 모두 거치는 퍼레이드 경로를 찾기가 어려웠습니다.
도전 과제
가능하다면 각 다리를 정확히 한 번씩 건너는 퍼레이드 경로를 찾아보세요. 만약 불가능하다면, 그 이유를 설명해 주세요.
탐사
강에 다리를 하나 더 놓으면 문제가 더 쉬워질까요, 아니면 더 어려워질까요?
노트
+
-
도전 과제
먼저 이 문제를 우리가 따라가야 할 간선이 있는 문제로 바꿔 생각해 봅시다. 지난주 "퍼레이드" 퍼즐에서 살펴본 것처럼, 홀수 개의 변이 들어오는 노드는 두 개 이하여야 합니다.
네 개의 노드 모두에 들어오는 간선의 수가 홀수이기 때문에 퍼레이드 경로를 찾는 것은 불가능합니다!
탐사
강에 다리를 하나 더 놓으면 문제를 해결하기가 훨씬 쉬워질 겁니다.
이 문제의 원인은 네 개의 노드 중 두 개에 짝수 개의 간선이 들어오게 되기 때문입니다.
그러면 들어오는 간선의 수가 홀수인 노드는 두 개만 남게 됩니다.