Jump to content

Seven Bridges of Königsberg

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
Original article: w:Seven Bridges of Königsberg
Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges

쾨니히스베르크의 일곱 다리(Seven Bridges of Königsberg)는 수학에서 역사적으로 주목할만한 문제입니다. 1736년에서 레온하르트 오일러(Leonhard Euler)에 의한 그의 음의 해는 그래프 이론(graph theory)의 토대를 마련하고[1] 토폴로지(topology)의 아이디어를 예고했습니다.[2]

프로이센(Prussia)에서 쾨니히스베르크(Königsberg)의 도시 (지금 칼리닌그라드, 러시아)는 프레벨 강(Pregel River) 양쪽, 두 개의 큰 섬—크네이포프(Kneiphof)와 로옴서(Lomse)—을 포함하여, 서로 연결, 또는 도시의 두 본토 일부에 연결되는, 일곱 다리를 놓았습니다. 문제는 한 번에 오직 하나의 그들 다리의 각각을 건너서 도시를 걸어서 통과하도록 고안하는 것이었습니다.

논리적인 임무를 명확하게 지정하는 방법으로, 다음의 둘 중 하나를 포함하는 해는 명백히 받아들일 수 없습니다:

  1. 다리 중에 하나를 통과하지 않고 섬 또는 본토 뚝에 도착하는 것, 또는
  2. 그의 다른 쪽 끝으로 건너지 않고 임의의 다리에 접근하는 것.

오일러는 문제가 해를 가지지 않음을 입증했습니다. 그가 직면한 어려움은 해석학의 적절한 기법의 개발, 및 수학적 엄격함을 갖는 이 주장을 확립하는 후속 테스트의 개발이었습니다.

Euler's analysis

오일러는 먼저 각 도시 내부의 경로 선택이 부적절하다고 지적했습니다. 경로의 유일한 중요한 특색은 건너는 다리의 순서열입니다. 이를 통해 그는 문제를 추상적 용어 (그래프 이론의 토대 마련)로 재공식화할 수 있었고, 도시 목록과 이것들을 연결하는 다리를 제외한 모든 특색을 제거했습니다. 현대적인 용어로, 각 땅 덩어리를 추상적인 "꼭짓점(vertex)" 또는 노드로 대체하고 각 다리를 추상 연결인 "가장자리(edge)"로 대체하며, 이는 해당 다리로 연결되는 꼭짓점 (땅 덩어리) 쌍을 기록하는 역할만 합니다. 결과 수학적 구조는 그래프(graph)입니다.

→ →

오직 연결 정보가 관련되기 때문에, 그래프 자체를 변경 없이 그래프의 그림 표현 모양이 어떤 식으로든 왜곡될 수 있습니다. 각 노드 쌍 사이에 가장자리가 있는지 여부만 중요합니다. 예를 들어, 그려진 가장자리가 직선인지 곡선인지 또는 한 노드가 다른 노드의 왼쪽 또는 오른쪽에 있는지는 중요하지 않습니다.

다음으로, 오일러는 (보행의 끝점을 제외하고) 다리를 통해 꼭짓점에 들어갈 때마다, 다리를 통해 꼭짓점을 떠나는 것을 관찰했습니다. 다시 말해서, 그래프에서 걷는 동안 비-종료 꼭짓점에 들어가는 횟수는 떠나는 횟수와 같습니다. 이제, 모든 다리가 정확히 한 번 건넜다면 각 도시에 대해 (시작과 끝으로 선택한 다리 제외) 해당 도시에 닿는 다리의 수는 짝수여야 합니다 (그 중 절반은 특정 순회는 육지를 "향하여" 횡단하고 나머지 절반은 육지에서 "멀리" 이동합니다. 어쨌든, 원래 문제에서 4개의 육지는 모두 홀수 개의 다리에 의해 연결됩니다 (하나는 5개의 다리와 연결되고 나머지 3개는 각각 3개의 다리와 연결됩니다). 기껏해야 두 개의 땅 덩어리가 보행의 종점 역할을 할 수 있기 때문에 각 다리를 한 번에 횡단하는 보행의 명제는 모순으로 이어집니다.

현대 언어에서, 오일러는 그래프를 통과할 가능성이 노드의 차수(degrees)에 따라 각 가장자리를 정확히 한 번 통과한다는 것을 보여줍니다. 노드의 차수는 노드에 닿는 가장자리의 수입니다. 오일러의 주장은 원하는 형태의 보행을 위한 필요 조건은 그래프가 연결되어 있고 홀수 차수의 노드가 정확히 0개 또는 2개라는 것을 보여줍니다. 이 조건은 역시 충분 조건임이 밝혀졌습니다—결과는 오일러에 의해 설명되고 나중에 카를 히어홀처(Carl Hierholzer)에 의해 입증되었습니다. 그러한 보행은 이제 그를 기리기 위해 오일러 경로(Eulerian path) 또는 오일러 보행(Euler walk)이라고 합니다. 게다가, 홀수 차수의 노드가 있으면, 임의의 오일러 경로는 그 중 하나에서 시작하여 다른 노드에서 끝납니다. 역사적인 쾨니히스베르크에 해당하는 그래프에는 홀수 차수의 노드가 4개 있으므로, 오일러 경로를 가질 수 없습니다.

다른 형태의 문제는 모든 다리를 가로지르고 같은 시작 점과 끝나는 점을 가지는 경로를 요구합니다. 그러한 보행을 오일러 회로(Eulerian circuit) 또는 오일러 여행(Euler tour)이라고 불립니다. 그러한 회로가 존재하는 것과 그래프가 연결되어 있고 모든 노드의 차수가 짝수인 것은 필요충분 조건입니다. 모든 오일러 회로는 오일러 경로이기도 하지만, 모든 오일러 경로가 오일러 ​​회로인 것은 아닙니다.

오일러의 연구는 1735년 8월 26일 상트페테르부르크 아카데미에 발표되었고, 1741년 Commentarii academiae scientiarum Petropolitanae 저널에 Solutio problematis ad geometriam situs pertinentis (위치 기하학과 관련된 문제의 해결책)으로 게재되었습니다.[3] 그것은 James R. Newman에 의해 The World of Mathematics에 영어 번역으로 유용합니다.

Significance in the history and philosophy of mathematics

수학의 역사에서, 오일러의 쾨니히스베르크 다리 문제의 해결책은 그래프 이론의 첫 번째 정리이자 네트워크 이론에서 첫 번째 진정한 증명으로 고려되며,[4] 현재 일반적으로 조합론(combinatorics)의 한 가지로 고려되는 주제입니다. 다른 유형의 조합론적 문제는 고대부터 고려되어 왔습니다.

추가적으로, 핵심 정보가 다리의 정확한 위치가 아니라 다리의 끝점 목록이라는 오일러의 인식은 토폴로지의 발전을 예측했습니다. 실제 레이아웃과 그래프 도식의 차이는 토폴로지가 대상의 단단한 모양과 관련이 없다는 아이디어의 좋은 예입니다.

따라서, 오일러가 인식한 것처럼, "위치의 기하학"은 "측정과 계산"에 관한 것이 아니라 보다 일반적인 것에 관한 것입니다. 그것은 수학이 "양(quantity)의 과학"이라는 전통적인 아리스토텔레스의 견해에 의문을 제기했습니다. 그 관점은 산술과 유클리드 기하학에 적합하지만 토폴로지와 현대 수학에서 연구되는 보다 추상적인 구조적 특징에는 적합하지 않습니다.[5]

철학자들은 오일러의 증명이 현실의 추상화나 모델에 관한 것이 아니라 다리의 실제 배열에 관한 것이라고 지적했습니다. 따라서 수학적 증명의 확실성은 현실에 직접 적용될 수 있습니다.[6] 그 증명은 역시 결과가 참이어야 하는 이유에 대한 통찰력을 제공하는 설명적입니다.[7]

Present state of the bridges

Modern map of Kaliningrad. Locations of the remaining bridges are highlighted in green, while those destroyed are highlighted in red.
In this picture of the Königsberg Cathedral, the bridge on the right is one of the two surviving bridges from Euler's time.

7개의 원래 다리 중 2개는 제2차 세계 대전 중 쾨니히스베르크 폭격에서 살아남지 못했습니다. 다른 2개는 나중에 철거되어 현대적인 고속도로로 대체되었습니다. 다른 세 개의 다리는 남아 있지만, 그 중 두 개만 오일러 시대의 것입니다 (하나는 1935년에 재건되었습니다).[8] 따라서, 2022년 기준, 오일러 문제와 관련된 같은 사이트에 5개의 다리가 존재합니다. 그래프 이론의 관점에서, 노드 중 두 개는 이제 차수가 2이고, 다른 두 개는 차수가 3입니다. 그러므로, 이제 오일러 경로가 가능하지만, 한 섬에서 시작하여 다른 섬에서 끝나야 합니다.[9]

Christchurch에 있는 University of Canterbury는 오래된 물리적 과학 도서관과 수학, 통계, 및 컴퓨터 과학과가 있는 Erskine 건물 사이의 잔디 구역에 다리 모형을 통합했습니다.[10] 강은 짧은 덤불로 대체되고 중앙 섬은 돌 토로(tōrō)를 자랑합니다. Rochester Institute of Technology은 2014년 개장한 아이스하키 경기장 진 폴리세니 센터 앞 포장도로에 퍼즐을 통합했고,[11] Georgia Institute of Technology도 2018년 7개 다리의 조경 예술 모형을 설치했습니다.[12]

Comparison of the graphs of the Seven bridges of Konigsberg (top) and Five room puzzle (bottom). The numbers denote the number of edges connected to each node. Nodes with an odd number of edges are shaded orange.

See also

References

  1. ^ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
  2. ^ Shields, Rob (December 2012). "Cultural Topology: The Seven Bridges of Königsburg 1736". Theory, Culture & Society. 29 (4–5): 43–57. doi:10.1177/0263276412451161. S2CID 146875675. Shields provides a discussion of the social significance of Euler's engagement with this popular problem and its significance as an example of (proto-)topological understanding applied to everyday life.
  3. ^ The Euler Archive, commentary on publication, and original text, in Latin.
  4. ^ Newman, M. E. J. The structure and function of complex networks (PDF). Department of Physics, University of Michigan.
  5. ^ Franklin, James (2014). An Aristotelian Realist Philosophy of Mathematics. Basingstoke: Palgrave Macmillan. p. 48-49, 96, 215, 225. ISBN 9781349486182.
  6. ^ Franklin, James (1994). "The formal sciences discover the philosophers' stone" (PDF). Studies in History and Philosophy of Science. 25 (4): 513–533. Bibcode:1994SHPSA..25..513F. doi:10.1016/0039-3681(94)90045-0. Retrieved 30 June 2021.
  7. ^ Räz, Tim (2018). "Euler's Königsberg: the explanatory power of mathematics". European Journal for Philosophy of Science. 8 (3): 331–346. doi:10.1007/s13194-017-0189-x. S2CID 125194454. Retrieved 30 June 2021.
  8. ^ Taylor, Peter (December 2000). "What Ever Happened to Those Bridges?". Australian Mathematics Trust. Archived from the original on 19 March 2012. Retrieved 11 November 2006.
  9. ^ Stallmann, Matthias (July 2006). "The 7/5 Bridges of Koenigsberg/Kaliningrad". Retrieved 11 November 2006.
  10. ^ "About – Mathematics and Statistics – University of Canterbury". math.canterbury.ac.nz. Archived from the original on 28 November 2016. Retrieved 4 November 2010.
  11. ^ RIT Womens Hockey [@RITWHKY] (19 August 2014). "@OnlyAtRIT do we put the 7 bridge math problem in the cement out front of the new hockey arena @PolisseniCenter #ROC" (Tweet) – via Twitter. {{cite web}}: Cite has empty unknown parameter: |dead-url= (help)
  12. ^ "The Seven Bridges of Königsberg". Georgia Tech. Retrieved March 24, 2022.{{cite web}}: CS1 maint: url-status (link)

External links

Wikimedia Commons has media related to Seven Bridges of Königsberg.

Retrieved from "https://dawoum.duckdns.org/w/index.php?title=Seven_Bridges_of_Königsberg&oldid=79835"