영재교육원 수학특강 그래프 이론- 오일러 경로

최적계획’, ‘그래프 이론’ 등 생활 속에서 일어나는 상황들을 수학적으로 간결하게 표현하고 해결하는 이산수학의 문제들이 많이 출제 되고 있다. 생활 속에서 맞닥뜨리는 문제들을 멋지게 해결해내느냐는 얼마나 유연하게 생각하고 창의적인 생각을 할 수 있느냐에 달려있지 않을까? 영재교육원 입학시험에서도 학생들에게 요구하는 것은 정확한 이론의 암기가 아니라 그를 응용한 창의적인 문제해결 능력이다.

기출문제 유형

▸오일러 경로 : 어떤 도형의 모든 선을 정확하게 한 번씩만 지나가는 경로
▸해밀턴 경로 : 도형에 있는 선은 반드시 모두 지나지 않아도 되지만 모든 정점을 한 번씩만 지나가는 경로

(1) 보기에서 오일러 경로가 없으면서 해밀턴 경로가 있는 도형을 찾으시오.
(2) (1)에서 찾은 도형들에 최소 개수의 선을 그어 오일러 경로가 있도록 만드시오.
▸다음 그림과 같이 수도권 전철은 1~8호선과 분당선, 국철, 인천 지하철 등이 있습니다. 방학 과제로 모든 환승역의 실태를 알아보아야 합니다. 현재 위치는 사당역인데, 하루 동안 모든 환승역을 돌아보고 다시 사당역으로 돌아오는 가장 효율적인 방법을 생각하여 쓰시오.

▸다음과 같은 동물원이 있습니다. 정문에서 출발하여 이 동물원의 동물들을 모두 관람하고 가장 빨리 되돌아오려고 합니다. 가장 빠른 경로와 그 때의 거리, 걸리는 시간을 구하시오.(1분 동안 100m를 걸을 수 있고, 동물을 관람하는데 각각 10분이 걸립니다.)<서울시교육청>

그림이 유난히 많은 문제의 특성상 기출문제는 이 정도만 소개하겠다. 문제에서 보여지듯 그래프이론의 기본 개념을 알면 풀 수 있는 문제로부터 어느 이론을 이용해서 접근해야할지 알기 힘든 문제까지 다양한 유형들이 출제되고 있다. 즉 정확한 이론의 이해를 요구하기 보다는, 가능한 다양한 방법으로 문제를 해결하기를 바라는 출제의도가 담겨 있는 것이다. 하지만 숨은 규칙을 발견할 수 있을 만큼 이론적 배경이나 원리를 이해하고 있다면 최소한 문제의 해석 정도라도 수월하지 않을까 싶다.

오일러 경로

먼저 오일러 경로부터 살펴보자.
퀴즈 문제로 많이 접해보았을 연필을 떼지 않고, 어느 선도 한 번만 지나도록 그리는 한붓그리기 문제들이 여기에 속한다. 한붓그리기는 한붓그리기가 가능한 도형과 불가능한 도형을 분류한 다음 찾아낸 공통점들을 통해 어떤 도형이 한붓그리기가 가능한지 여부를 알아볼 수 있다. 그 과정은 생략하고 결론만 정리하면 다음과 같다.

꼭지점과 선으로 이루어진 도형에서 한 꼭지점에 연결된 변의 수가 짝수 개인 점을 짝수점(점 A와 점 C), 홀수 개인 점을 홀수점(점 D와 점 B)이라고 할 때,(1) 홀수점이 없는 도형은 어느 점에서 출발하여도 한붓그리기가 가능하며, 이 때 모든 선을 한 번씩 지나 출발점으로 돌아오는 길을 ‘오일러 순환길’ 이라고 한다.
(2) 홀수점이 2개인 도형은 한 홀수점에서 출발하여야만 한붓그리기가 가능하고 다른 홀수점에서 끝난다. 이 때 한 번씩 지나간 길을 ‘오일러 길’이라고 한다.

그럼 홀수점이 없거나 2개일 경우만 한붓그리기가 가능한 이유를 잠깐 생각해 보자.
ⅰ) 한 점을 지나는 길이 짝수 개일 때, 어떤 길을 이용하여 그 점을 향해 들어왔다면, 다른 길로 나가기를 선의 개수의 절반만큼 반복하여 모든 길을 한 번씩 지날 수 있게 된다. 즉 다음 그림의 점 A와 같이 4개의 선이 만나는 점은 들어오고 나가기를 2번 반복하고, 점 B과 같이 2개의 선이 만나는 점은 들어오고 나가기를 1번하여 점과 이어진 모든 선을 한 번씩 그릴 수 있게 된다. 따라서 이 경우에는 어느 점에서 출발하더라도 다시 출발점으로 돌아올 수밖에 없는 순환길이 만들어지는 것이다.

ⅱ) 홀수점이 2개인 경우는 각각의 홀수 점에서 들어오거나, 나가기를 한 번씩밖에 할 수가 없다. 따라서 홀수 점 2개(점 C와 점 D) 중 한 개의 점 C에서 나가기(출발)를 했다면, 다른 홀수 점 D로 들어가기(도착)를 해서 한붓그리기를 완성할 수 있다.

오일러 순환길을 이용한 다양한 문제
생활에서 볼 수 있는 상황들을 점과 선으로 간단하게 표현한 다음 오일러 이론을 이용하여 문제를 해결한 몇 가지 경우를 살펴보자.
▸잘 알려진 쾨니히스베르크의 다리 문제이다. 산책을 하면서 7개의 다리를 모두 한 번씩만 지나 출발지점으로 돌아올 수 있는 방법이 있는지를 알아보자.

먼저 그림을 점과 선으로 단순화 하는 작업이 필요하다. 강으로 나누어진 지역을 점 A, B, C, D로 하고, 건너야하는 다리를 선으로 나타내면 위의 오른쪽 그림처럼 된다. 점 A, B, C, D 모두 홀수점이므로 한붓그리기가 불가능한 도형임을 알 수 있다. 결국 모든 길을 한 번씩 지나 출발점으로 돌아오는 길은 없다.

▸아래 그림은 11개의 전시실과 전시실을 연결하는 17개의 문으로 이루어진 박물관의 평면도이다. 모든 문을 한 번씩만 통과할 수 있는 방법을 찾아보자.

11개의 전시실을 각각 점으로 17개의 문을 선으로 나타내면, 하나의 홀수점()에서 출발하여 다른 홀수점()으로 도착하는 오일러 길이 완성된다. 점과 선으로 찾은 오일러 길을 따라 모든 문을 한 번씩만 통과하는 방법은 직접 그려보시길...


▸ 아래 그림에서 8개의 방은 인접한 방들과 서로 통하는 문이 모두 하나씩 있습니다. 한 방에서 시작하여 모든 방과 문을 한 번씩 지날 수 있습니까? 있으면 지나가는 길을 그리고, 없으면 그 이유를 설명하시오

경향신문