쾨니히스베르크의 다리 문제
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
쾨니히스베르크의 다리 문제는 18세기 쾨니히스베르크(현재 칼리닌그라드)에 있던 일곱 개의 다리를 모두 한 번씩만 건너서 출발점으로 돌아올 수 있는지를 묻는 수학 문제입니다. 레온하르트 오일러는 이 문제를 그래프 이론으로 변환하여 분석했으며, 모든 다리를 한 번씩 건너서 돌아오는 경로는 존재하지 않음을 증명했습니다. 오일러의 분석은 그래프의 정점 차수가 짝수여야 한다는 점을 밝혔고, 이는 그래프 이론과 위상수학 발전에 기여했습니다. 현재 쾨니히스베르크에는 다리 개수가 줄어 오일러 경로가 가능하게 되었으며, 이 문제는 현대에도 다양한 형태로 응용되고 있습니다.
https://www.google.com/maps?ie=UTF8&om=1&z=16&ll=54.705569,20.511389&spn=0.010674,0.01899 현재 쾨니히스베르크 다리 링크 (현재 다리 개수는 과거와 다름)]]
오일러는 각 육지 내에서의 경로 선택은 중요하지 않으며, 다리를 건너는 순서만이 경로의 유일한 특징이라고 지적했다. 그는 육지와 다리를 제외한 모든 특징을 제거하고, 육지를 정점으로, 다리를 변으로 대체하여 문제를 추상적인 그래프 형태로 재구성했다.[3]
2. 쾨니히스베르크의 다리 문제
18세기 초 프로이센 왕국 동부 동프로이센의 수도였던 쾨니히스베르크(현 러시아 연방 칼리닌그라드)에는 프레겔 강이 흐르고 있었고, 일곱 개의 다리가 놓여 있었다. 마을 사람들은 "프레겔 강에 놓인 7개의 다리를 두 번 지나지 않고 모두 건너서 원래 출발했던 곳으로 돌아올 수 있을까? 단, 어디에서 출발해도 좋다."라는 문제를 제기하였다.
1736년, 레온하르트 오일러는 이 문제를 그래프로 바꿔서 생각했다.
→
이 그래프가 한붓 그리기 가능하다면, 쾨니히스베르크의 다리를 모두 한 번씩 건너서 돌아오는 경로가 존재하게 된다. 그리고 오일러는 이 그래프가 한붓 그리기가 불가능함을 증명하여 쾨니히스베르크의 다리 문제를 부정적으로 해결했다.
2. 1. 문제의 내용
18세기 초 프로이센 왕국 동부 동프로이센의 수도였던 쾨니히스베르크(현 러시아 연방 칼리닌그라드)에는 프레겔 강이 흐르고 있었고, 일곱 개의 다리가 놓여 있었다. 마을 사람들은 "프레겔 강에 놓인 7개의 다리를 두 번 지나지 않고 모두 건너서 원래 출발했던 곳으로 돌아올 수 있을까? 단, 어디에서 출발해도 좋다."라는 문제를 제기하였다.
2. 2. 그래프 이론과의 연관성
1736년, 레온하르트 오일러는 이 문제를 그래프로 바꿔서 생각했다.
→
이 그래프가 한붓 그리기 가능하다면, 쾨니히스베르크의 다리를 모두 한 번씩 건너서 돌아오는 경로가 존재하게 된다. 그리고 오일러는 이 그래프가 한붓 그리기가 불가능함을 증명하여 쾨니히스베르크의 다리 문제를 부정적으로 해결했다.
3. 오일러의 분석
→
그래프 그림 표현의 모양은 그래프 자체를 변경하지 않고 왜곡될 수 있으며, 각 노드 쌍 사이의 변의 수만이 중요하다.[3] 오일러는 다리를 통해 정점에 들어갈 때마다 다리를 통해 정점을 나간다는 것을 관찰했다. 즉, 그래프에서 보행 중 비단말 정점에 들어가는 횟수는 나가는 횟수와 같다. 모든 다리가 정확히 한 번 통과된다면, 각 육지(시작점과 끝점 제외)에 닿는 다리의 수는 짝수여야 한다. 그러나 원래 문제의 네 육지 모두 홀수 개의 다리에 닿으므로, 각 다리를 한 번씩 통과하는 보행은 불가능하다.[3]
현대 용어로, 오일러는 그래프의 각 변을 정확히 한 번 통과하는 보행(오일러 경로)의 가능성은 노드의 차수에 달려 있음을 보였다. 그래프가 연결되어 있고 홀수 차수를 가진 노드가 0개 또는 2개여야 한다는 조건은 오일러 경로를 위한 필요충분 조건이며, 이는 카를 히어홀처에 의해 증명되었다. 홀수 차수의 노드가 있다면, 모든 오일러 경로는 그중 하나에서 시작하여 다른 하나에서 끝난다. 쾨니히스베르크에 해당하는 그래프는 4개의 홀수 차수 노드를 가지므로 오일러 경로를 가질 수 없다.[3]
모든 다리를 통과하고 시작점과 끝점이 같은 경로인 오일러 회로는 그래프가 연결되어 있고 모든 노드가 짝수 차수를 가질 경우에만 존재한다. 모든 오일러 회로는 오일러 경로이지만, 모든 오일러 경로가 오일러 회로는 아니다.[3]
오일러의 연구는 1736년 ''Commentarii academiae scientiarum Petropolitanae''에 ''Solutio problematis ad geometriam situs pertinentis''(위치 기하학에 관한 문제의 해결)로 출판되었다.[3]
3. 1. 오일러 경로와 오일러 회로
오일러는 각 육지 내에서의 경로 선택은 중요하지 않으며, 다리를 건너는 순서만이 경로의 유일한 특징이라고 지적했다. 그는 육지와 다리를 제외한 모든 특징을 제거하고, 육지를 정점으로, 다리를 변으로 대체하여 문제를 추상적인 그래프 형태로 재구성했다.[3]
→
→
그래프 그림 표현의 모양은 그래프 자체를 변경하지 않고 왜곡될 수 있으며, 각 노드 쌍 사이의 변의 수만이 중요하다.[3] 오일러는 다리를 통해 정점에 들어갈 때마다 다리를 통해 정점을 나간다는 것을 관찰했다. 즉, 그래프에서 보행 중 비단말 정점에 들어가는 횟수는 나가는 횟수와 같다. 모든 다리가 정확히 한 번 통과된다면, 각 육지(시작점과 끝점 제외)에 닿는 다리의 수는 짝수여야 한다. 그러나 원래 문제의 네 육지 모두 홀수 개의 다리에 닿으므로, 각 다리를 한 번씩 통과하는 보행은 불가능하다.[3]
현대 용어로, 오일러는 그래프의 각 변을 정확히 한 번 통과하는 보행(오일러 경로)의 가능성은 노드의 차수에 달려 있음을 보였다. 그래프가 연결되어 있고 홀수 차수를 가진 노드가 0개 또는 2개여야 한다는 조건은 오일러 경로를 위한 필요충분 조건이며, 이는 카를 히어홀처에 의해 증명되었다. 홀수 차수의 노드가 있다면, 모든 오일러 경로는 그중 하나에서 시작하여 다른 하나에서 끝난다. 쾨니히스베르크에 해당하는 그래프는 4개의 홀수 차수 노드를 가지므로 오일러 경로를 가질 수 없다.[3]
모든 다리를 통과하고 시작점과 끝점이 같은 경로인 오일러 회로는 그래프가 연결되어 있고 모든 노드가 짝수 차수를 가질 경우에만 존재한다. 모든 오일러 회로는 오일러 경로이지만, 모든 오일러 경로가 오일러 회로는 아니다.[3]
오일러의 연구는 1736년 ''Commentarii academiae scientiarum Petropolitanae''에 ''Solutio problematis ad geometriam situs pertinentis''(위치 기하학에 관한 문제의 해결)로 출판되었다.[3]
4. 한붓그리기 판정법 및 해법
어떤 연결 그래프가 한붓 그리기가 가능한 경우의 필요충분 조건은 다음 조건 중 어느 하나가 성립하는 것이다([오일러 경로 참조).
- 모든 꼭짓점의 차수(꼭짓점에 연결된 변의 수)가 짝수 → 붓이 시작점으로 돌아오는 경우(폐로)
- 차수가 홀수인 꼭짓점의 수가 2개이고, 나머지 꼭짓점의 차수는 모두 짝수 → 붓이 시작점으로 돌아오지 않는 경우(폐로가 아닌 경로)
모든 꼭짓점의 차수가 짝수이면 어떤 꼭짓점에서 출발하여 원래의 꼭짓점으로 돌아오는 경로를 만들 수 있다. 만약 아직 지나가지 않은 경로가 있다면, 앞서의 경로에서 어떤 꼭짓점을 선택하고, 거기에서 샛길을 통해 그 꼭짓점으로 돌아오는 경로를 추가하여 수정하는 것을 반복하면 된다.
차수가 홀수인 꼭짓점의 수가 2개이고, 나머지 꼭짓점의 차수가 모두 짝수이면 어떤 홀수 꼭짓점에서 출발하여 다른 홀수 꼭짓점으로 나가는 경로를 만들 수 있다. 만약 아직 지나가지 않은 경로가 있다면, 앞서의 경로에서 어떤 꼭짓점을 선택하고, 거기에서 샛길을 통해 그 꼭짓점으로 돌아오는 경로를 추가하여 수정하는 것을 반복하면 된다.
4. 1. 한붓그리기 판정법
어떤 연결 그래프가 한붓 그리기가 가능한 경우의 필요충분 조건은 다음 조건 중 어느 하나가 성립하는 것이다([오일러 경로 참조).- 모든 꼭짓점의 차수(꼭짓점에 연결된 변의 수)가 짝수 → 붓이 시작점으로 돌아오는 경우(폐로)
- 차수가 홀수인 꼭짓점의 수가 2개이고, 나머지 꼭짓점의 차수는 모두 짝수 → 붓이 시작점으로 돌아오지 않는 경우(폐로가 아닌 경로)
4. 2. 한붓그리기 해법
모든 꼭짓점의 차수가 짝수이면 어떤 꼭짓점에서 출발하여 원래의 꼭짓점으로 돌아오는 경로를 만들 수 있다. 만약 아직 지나가지 않은 경로가 있다면, 앞서의 경로에서 어떤 꼭짓점을 선택하고, 거기에서 샛길을 통해 그 꼭짓점으로 돌아오는 경로를 추가하여 수정하는 것을 반복하면 된다.차수가 홀수인 꼭짓점의 수가 2개이고, 나머지 꼭짓점의 차수가 모두 짝수이면 어떤 홀수 꼭짓점에서 출발하여 다른 홀수 꼭짓점으로 나가는 경로를 만들 수 있다. 만약 아직 지나가지 않은 경로가 있다면, 앞서의 경로에서 어떤 꼭짓점을 선택하고, 거기에서 샛길을 통해 그 꼭짓점으로 돌아오는 경로를 추가하여 수정하는 것을 반복하면 된다.
5. 수학사와 철학에 미친 영향
그래프 이론의 첫 번째 정리이자 네트워크 이론의 첫 번째 진정한 증명으로 간주되는 쾨니히스베르크의 다리 문제에 대한 오일러의 해는 수학사에 큰 영향을 미쳤다.[4] 이 이론은 현재 조합론의 한 분야로 여겨진다. 오일러는 다리의 수와 그 끝점 목록(정확한 위치가 아니라)이 핵심 정보라는 것을 인식하여 위상수학의 발전을 예고했다. 실제 레이아웃과 그래프 개략도의 차이는 위상수학이 물체의 강성 형태에 관여하지 않는다는 점을 보여준다.
오일러가 인식했듯이 "위치의 기하학"은 "측정과 계산"이 아닌 더 일반적인 것에 관한 것이며, 이는 수학이 "양의 과학"이라는 아리스토텔레스적 관점에 의문을 제기한다.[5] 이 관점은 산술과 유클리드 기하학에는 맞지만, 위상수학과 현대 수학에서 연구되는 더 추상적인 구조적 특징에는 맞지 않는다.
철학자들은 오일러의 증명이 현실의 추상화나 모델이 아닌, 다리의 실제 배열에 직접적으로 관한 것이라고 언급했다. 따라서 수학적 증명의 확실성은 현실에 직접 적용될 수 있다.[6] 또한 이 증명은 결과가 왜 참이어야 하는지에 대한 통찰력을 제공한다.[7]
6. 다리의 현재 상태
일곱 개의 원래 다리 중 두 개는 제2차 세계 대전 중 쾨니히스베르크 폭격에서 살아남지 못했다.[8] 다른 두 개는 나중에 철거되어 고속도로로 대체되었다. 나머지 세 개의 다리가 남아 있으며, 그중 두 개는 오일러 시대의 것이다(하나는 1935년에 재건되었다).[8] 이러한 변화로 오일러의 문제와 관련된 동일한 위치에 다섯 개의 다리가 남게 되었다. 그래프 이론 측면에서, 두 개의 노드는 이제 차수가 2이고, 다른 두 개는 차수가 3이다. 따라서 오일러 경로는 이제 가능하지만, 한 섬에서 시작하여 다른 섬에서 끝나야 한다.[9]
크라이스트처치의 캔터베리 대학교는 구 물리학 도서관과 수학, 통계 및 컴퓨터 과학부가 있는 어스킨 빌딩 사이의 잔디밭에 다리의 모형을 설치했다.[10] 강은 짧은 덤불로 대체되었고, 중앙 섬에는 돌 등롱이 있다. 로체스터 공과대학교는 2014년에 개장한 아이스 하키 경기장인 진 폴리세니 센터 앞 보도에 퍼즐을 통합했고,[11] 조지아 공과대학교도 2018년에 일곱 개의 다리 랜드스케이프 아트 모형을 설치했다.[12]
퍼즐의 인기 있는 변형은 브리스톨 다리 걷기이다.[13] 역사적인 쾨니히스베르크처럼 브리스톨은 두 개의 강둑과 두 개의 강 섬을 차지하고 있다.[14] 그러나 브리스톨에 있는 45개의 주요 다리의 구성은 오일러 회로가 존재하도록 한다.[15] 이 사이클은 책[15]과 뉴스 보도[16][17]를 통해 대중화되었으며 다양한 자선 행사에서 다루어졌다.[18]
7. 현대적 응용 및 변형
참조
[1]
간행물
Solutio problematis ad geometriam situs pertinentis
https://archive.org/[...]
2024-09-21
[2]
간행물
Cultural Topology: The Seven Bridges of Königsburg 1736
2012-12
[3]
웹사이트
The Euler Archive
https://scholarlycom[...]
[4]
서적
The structure and function of complex networks
http://www-personal.[...]
Department of Physics, University of Michigan
[5]
서적
An Aristotelian Realist Philosophy of Mathematics
https://books.google[...]
Palgrave Macmillan
2014
[6]
간행물
The formal sciences discover the philosophers' stone
http://www.maths.uns[...]
2021-06-30
[7]
간행물
Euler's Königsberg: the explanatory power of mathematics
https://link.springe[...]
2021-06-30
[8]
웹사이트
What ''Ever'' Happened to Those Bridges?
http://www.amt.canbe[...]
Australian Mathematics Trust
2000-12
[9]
웹사이트
The 7/5 Bridges of Koenigsberg/Kaliningrad
http://www.csc.ncsu.[...]
2006-07
[10]
웹사이트
About – Mathematics and Statistics – University of Canterbury
http://www.math.cant[...]
2010-11-04
[11]
트윗
"@OnlyAtRIT do we put the 7 bridge math problem in the cement out front of the new hockey arena @PolisseniCenter #ROC"
2014-08-19
[12]
웹사이트
The Seven Bridges of Königsberg
https://arts.gatech.[...]
2022-03-24
[13]
서적
Solving the Bristol Bridge problem
Oxford University Press
2014-07-01
[14]
웹사이트
Bristol Bridges Walk
https://www.alltrail[...]
2023-11-22
[15]
서적
From Brycgstow to Bristol in 45 Bridges
Bristol Books
2019-06-06
[16]
뉴스
Bristol's 42 crossings -- Not a bridge too far for maths ace
Bristol Post
2013-03-01
[17]
뉴스
Taking on the Bristol Bridges Challenge.
https://www.bristol2[...]
Bristol24/7
2023-11-22
[18]
뉴스
This is why people will be paying £1 as they cross bridges in Bristol next week
Bristol Post
2019-10-02
[19]
뉴스
【知っとくトク】鉄道でぐるり一筆書き 長距離は運賃安く 途中下車も可能
https://www.nikkei.c[...]
日本経済新聞
2018-04-23
[20]
문서
다리를 한 번만 건너면서 처음 시작한 위치로 돌아오는 길이 있으려면 짝수여야 한다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com