수학으로의 여행 을 읽고

소개

참고

목차

없음

본문내용

* 거리를 청소하는 차가 한번 청소한 거리를 다시 지나가지 않는 것이 효율적이다. 어떤 경로로 청소하는 것이 가장 효율적일까?

* 배낭 여행을 떠날 때 최소의 경비를 들여서 원하는 도시를 다 방문하려면 어떻게 계획을 세우는 것이 현명한가?

위의 질문들은 그래프 이론이 적용되는 예이다. 그래프 이론의 역사는 1736년 쾨니히스베르크(Konigsberg)도시에 있는 다리 문제를 다룬 오일러(Euler)의 논문 “쾨니히스베르크 7개의 다리(The seven Bridges of Konigsberg)"로부터 시작되었다. 그 후, 영국의 수학자 해밀턴(W. R. Hemilton)에 의하여, 여행로를 따라서 각 도시를 단 한 번만 지나가는 세계여행 코스를 찾아내라는 ‘해밀턴의 문제가’ 제시되었다. 이것은 여행시간이나 여비를 고려한다면 여행업자가 언제나 직면하는 문제이다. 쾨니히스베르크 다리 문제는 다음과 같다.


유명한 철학자 칸트가 여생을 보낸 쾨니히스베르크에 프레겔 강이 흐르는데, 이 강에 7개의 다리가 있다[그림1]. 시민들은 이 다리를 두 번 건너지 않고 모든 다리를 한번씩만 건너서 산책할 수 있을까? 하고 질문을 하였다. 쾨니히스베르크 다리 문제에 프레겔 강의 넓이나 땅의 모양이 답에 영향을 주지 않는가? 그렇지 않다, 쾨니히스베르크 다리 문제는 육지가 다리에 의하여 어떻게 연결되어 있는지가 중요하다. 다리의 모양이나 길이는 상관이 없다. 쾨니히스베르크의 각 육지를 한 점으로 표현하고 다리를 곡선으로 표현하면 [그림2]처럼 된다.

흔히 한붓그리기로 잘 알려진 위 문제는 그래프에서의 홀수점과 짝수점을 알아야 한다. 간단히 말해 홀수점은 선의 시작과 끝이고 짝수점은 지나가는 선이다. 한붓그리기가 가능하려면, 홀수점이 0개이거나 2개일 때만 가능하다. 그 이유는 점으로 들어가는 선이 있으면 나오는 선도 있어야 하기 때문이다. 모든 점들에 선이 짝수개 연결되어 있다면, 한 선으로 들어가면 다른 한 선으로는 나올 수 있다. 따라서 한붓그리기가 가능하다. 홀수점이 2개가 있다면 상황이 좀 다르다. 만약 짝수점에서 출발한다면, 홀수점으로 `들어왔을 때` 나갈 길이 없게 돼서 나갈 길이 없게 되어 그릴 수 없다. 하지만 홀수점에서 출발한다면, 홀수점에서 `나가서` 마지막에 다른 홀수점으로 `들어오면` 된다.
위 그림에서는 애초에 짝수점이 없고 A-5개 B-3개 C-3개 D-3개으로 홀수점만 4개 있어 같은곳을 지나지 않고 모든 다리를 건너는 것은 불가능하다.

참고자료

· 없음