그래프 이론이라고 들어 보셨습니까? 유한개의 점과 변으로 이루어진 도형을 연구하는 학문이지요. 전 그래프 연구를하던 중 그 어떤 복잡한 미로도 그래프를 이용해 쉽게 길을 찾을 수 있다는 것을 알아 냈습니다. 고대 미로는 한붓그리기라는 말이 앞에서도 나왔지요? 한붓그리기를 누가 연구했는지 아십니까? 바로 저랍니다. 하하~.
누구나 한 번쯤 복잡한 전시관에서 길을 잃은 기억이 있을 겁니다. 이 작품 아까 봤던 건데! 하면서 말이지요. 걸어도 그 자리가 그 자리인 미로와도 같은 전시관! 제가 길을 잃지 않는 방법을 알려 드릴게요.
모든 전시를 다 보고 나와야겠지요? 보통 전시관 입구나 팸플릿을 보면 전시관 안내도나 배치도가 있습니다.
우선 전시물마다 점을 찍고 알파벳을 정하세요. 그리고 입구부터 차례로 모든 길을 갈 수 있도록 점을 잇습니다. 제가 찍은 점에 의하면 A→B→C→D→E→F→G→H→I→J→K→L 순서대로 전시를 보고 나오면 됩니다. 모든 전시는 한붓그리기가 가능합니다. 전시관 배치도를 가지고 한붓그리기를 해 보세요.
미로의 길이 모두 한붓그리기는 아니에요. 모든 길을 다 지나지 않아도 되는 미로도 있으니까요. 그럴 경우엔 미로를단순화해서 그래프로 나타내면 한눈에 길이 보입니다. 진짜로 그런지 직접 그래프를 그려 확인해 볼까요?
주어진 미로의 모든 길목에 알파벳을 적어 넣습니다. 그러고 보니 출발점인 A에서 갈 수 있는 길은 오직 B밖에 없네요. A에서 B로 직선을 긋습니다. B에서 갈 수 있는 길은 C와 D. 그런데 C는 막힌 길이므로 D를 B의 오른쪽에 적고 C를 B의 위나 아래에 적습니다. D에서 갈 수 있는 길은 Q와 E, F 지요. E는 막힌 길이므로 D의 위나 아래에 적습니다. Q에선 P, R, S로 갈 수 있지만 결국 다 막힌 길입니다. 따라서 Q도 D의 위나 아래에 적습니다. F는 D의 오른쪽에 적습니다. 이런 방식으로 모든 알파벳을 나타내면 미로 그래프를 만들 수 있습니다.
그래프를 다 나타내고 보니 출발점 A에서 도착점 T까지 가장 빨리 방법은 A→B→D→F→H→I→J→T인 것을 알 수 있습니다. 어떤 미로도 이 방법으로 길을 찾을 수 있지요. 하지만 단점도 있어요. 복잡한 미로의 경우 그래프 그리는 시간이 너무 많이 걸린다는 점이에요. 하지만 길은 반드시 찾을 수 있답니다.
그래프 가치는 무궁무진합니다. 미로와도 같은 지하철 노선이나 버스 노선을 그래프 이론을 이용해 쉽게 그릴 수 있고 인터넷망, 전화 통신망, 은행 전산망 등에도 그래프 이론이 활용되기 때문이에요.
오일러 회로나 경로를 따르는 한붓그리기
한붓그리기를 활용하면 길을 잃지도 않을뿐더러 왔던 길을 다시 가지 않아 효율적이다. 하지만 언제나 한붓그리기가 가능한 것은 아니다. 한붓그리기가 가능하려면 오일러 회로거나 오일러 경로여야 한다. 오일러 회로는 어떤 점에서 시작해도 모든 변을 다지나 그 점으로 돌아오는 도형을 말한다. 이 도형은 임의의 꼭짓점에 연결된 변이 모두 짝수 개다. 오일러 경로는 꼭짓점에 연결된 변이 홀수 개인 점에서 시작해 모든 변을 다 돌고 다른 홀수 개인 점에서 끝나는 도형으로 시작점과 끝점을 빼고 모두 짝수 개의 점으로 구성된다.
모든 길을 다 지나갈 필요는 없다
오일러 회로와 경로는 모든 변, 즉 모든 길을 다 지난다. 하지만 전시를 볼 때 전시물만 보면 되지 모든 길을 다 지날필요는 없다. 모든 점만 다지나면 된다는 이야기다. 이를 연구한 사람이 해밀턴이다. 해밀턴은 모든 꼭짓점을 단 한 번만 지나는 회로와 경로를만들었다. 회로는 시작점과 끝점이 같을 때를, 경로는 다를 때를 말한다. 하지만 안타깝게도 오일러 회로나 경로와 달리 해밀턴 회로와 경로가 존재하는 조건은 밝혀지지 않았다.
▼관련기사를 계속 보시려면?
미로 탈출의 명수를 찾아라!
기호 1 미로를 처음 탈출한 사람은 바로 나!
기호 2 미로는 천국으로 가는 길
기호 3 탈출할 수 있는 미로와 없는 미로
기호 4 미로 탈출의 열쇠는 그래프!
기호 5 예술가의 고뇌와 닮은 미로
미로대회 우승자는 누구?
미로를 체험하러 떠나요~!
