Koenigsberg Bridge Problem
18세기 동(東)프로이센의 수도 쾨니히스베르크 (현재의 칼리닌그라드) 에 있던 프레겔강(江)의 다리건너기를 제재로 한 초기의 위상기하학 문제이다. 쾨니히스베르크는 프레겔강에 의해 과 같이 A,B,C,D의 4지역으로 나누어지고, 이들 지역을 잇는 7개의 다리 a,b,c,d,e,f,g가 놓여 있었다. 그런데 이 7개의 다리에 대해 “같은 다리를 두 번 건너는 일 없이 이들 다리를 모두 건너라”는 문제가 누군가에 의해 출제되었다. 이것은 ‘한붓그리기’의 문제이며, 위상기하학의 기초적인 문제로서 유명하다 ........ 이 문제에서 각 지역을 점으로, 다리를 선으로 나타내어 점 A,B,C,D는 각 지역이고, 선은 7개의 다리이다. 점 A를 출발하여 선을 따라 연필을 떼지 않고 어느 선도 한 번만 지나도록 그릴 수 있다면, 이 문제는 해결되는 셈이다. 그러나 이것은 불가능하다는 것이 스위스의 수학자 L.오일러에 의해 밝혀졌다. ........ (쾨니히스베르크의 다리건너기 문제 : Yahoo)
그래프 이론 (Graph Theory) 의 첫 논문은 1736 년 레오나드 오일러 (Leonhard Euler) 의 것이었다. 그 논문은 현재 쾨닉스베르그 (Königsberg) 다리 문제에 대한 해법을 포함한 일반적인 그래프 이론을 제시하였다. 쾨닉스베르그 (Königsberg, 지금 러시아의 칼리닌그라드) 에 있는 프레겔 강에 있는 두 개의 섬이 그림 7 과 같이 다리에 의해 각각 연결되어 있고 강둑도 다리로 연결되어 있다. 문제는 어떤 위치 - A, B, C, 또는 D - 에서 출발하여 ; 각각의 다리를 한 번만 건너서 ; 출발점으로 돌아오는 것이다.
그림 7 쾨닉스베르그 다리
그림 8 쾨닉스베르그 다리의 그래프 모델
이 다리의 구성은 그림 8 과 같이 그래프로 모델화할 수 있다. 정점은 위치를 나타내고 간선은 다리를 나타낸다. 쾨닉스베르그 다리 문제는 그림 8 의 그래프에서 모든 에지와 모든 정점이 다 포함되어 있는 사이클을 찾는 문제로 변형된다. 오일러의 업적을 기리어 그래프 G 안의 모든 정점과 모든 에지가 포함되는 사이클을 오일러 사이클 (Euler cycle) 이라 부른다. 서론의 논의로부터, 그림 8 의 그래프 안에는 정점 A 에 부속된 모서리선이 홀수이므로 오일러 사이클은 없다 (사실, 그림 8 의 그래프에서, 모든 정점은 홀수 개의 간선이 부속되어 있다).
그래프 G 가 오일러 사이클을 가지면, G 는 연결되어 있고 각 정점은 짝수 차수이다.
G 가 연결된 그래프이고 모든 정점이 짝수 차수를 가지면 G 는 오일러 사이클을 가진다.
............ (경로와 사이클 (Paths and Cycles) : Richard Johnsonbaugh)
term :
그래프 이론 (Graph Theory) 순회판매원 문제 (Traveling Salesman Problem) 해밀턴의 사이클 문제 (Hamiltonian Cycle Problem) 쾨니히스베르크의 다리건너기 문제 (Koenigsberg Bridge Problem)
site :
video :
2회 생활 속 기하학 : 수학으로 푸는 세상의 비밀 - YTN 사이언스 : 박경미 수학스토리텔러 홍익대교수, 2013/11/21...... 동영상 19분부터 설명함
세기의 수학자들 : 수학으로 푸는 세상의 비밀 - YTN 사이언스: 박경미 수학스토리텔러 홍익대교수, 2014/06/18 .... 동영상 14분부터 설명함