섬 둘, 강둑 둘, 다리 일곱입니다. 강둑별로 다리를 세면 3, 3, 3, 5가 되고 차수를 더하면 3 + 3 + 3 + 5 = 14입니다(첫 번째 링크. 세 번째 링크는 3 × 3 + 5로 같은 14를 얻는데, 더 빠른 묶음입니다). 그 합의 절반이 다리의 수입니다. 두 번째 링크는 나누어 7을 줍니다. 이 관계는 이 지도에만 특별한 것이 아닙니다. 모든 다리가 두 강둑에 기여하므로 차수는 변 수의 두 배여야 합니다. 네 번째 링크 4 × 3/2 = 6은 다리로 이을 수 있는 육지 쌍의 수이며, 여섯 쌍에 일곱 다리가 놓이므로 적어도 한 쌍의 육지는 다리 하나가 아니라 둘로 이어집니다.
오일러의 논거는 이렇습니다. 각 다리를 한 번씩 건너는 산책은 지나가는 각 육지에 들어가고 나오는 일이 짝을 이루어야 하므로, 멈추는 점으로 쓰이는 모든 꼭짓점은 짝수 차수를 갖습니다. 예외는 산책의 첫 꼭짓점과 마지막 꼭짓점뿐이며, 그 둘뿐입니다. 쾨니히스베르크에는 홀수 차수 꼭짓점이 넷이므로 요구한 종류의 산책은 존재하지 않고, 증명은 누군가 강을 측정하기 전에 이미 끝납니다. 이 논문이 퍼즐 풀이가 아니라 그래프 이론의 첫 정리로 다루어지는 이유입니다. 거리, 강둑의 모양, 프레골리강의 너비는 모두 무관하며 오일러도 그렇게 말합니다. 문제를 크기의 기하가 아니라 위치의 기하에 놓은 것입니다. 일곱 다리 중 둘은 1944년에 파괴되어 다시 세워지지 않았으므로 오늘날 이 질문은 관광객의 것입니다. 여기의 산수는 1735년에 오일러에게 보내진 지도에 관한 것입니다.
답
14
읽는 방법
네 차수의 합입니다. 두 번째 링크는 그것을 절반으로 나눠 일곱 다리를 만들고, 세 번째는 다른 방식으로 더하며, 네 번째는 육지 쌍의 수를 셉니다.
출처
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.