지하철 노선도를 보면 역과 역의 연결 상태를 한눈에 파악할 수 있어 편리하다. 각 역을 점으로 표현해 역과 역을 선으로 연결하고 있다.(그림 1) 점과 선으로 중요한 정보를 전달하고 있는 셈이다. 수학에선 점과 선으로 그려진 그림을 그래프라고 한다. 특히 그래프의 점은 꼭지점, 그래프의 선을 변이라 하고, 한 꼭지점에 연결된 변의 개수를 그 꼭지점의 차수라고 한다. 지하철 노선도에서 서울역은 차수가 4인 꼭지점이다.

관찰하고 추측하기

1. 옛 프러시아의 쾨니히스베르크를 흐르던 프레겔강에는 7개의 다리가 있다. 한 곳에서 출발해 7개의 다리를 한 번씩 모두 건너 제자리로 돌아올 수 있을까?(그림 2) 당시 사람들은 수많은 실제 경험을 통해 7개의 다리를 모두 건너 제자리로 돌아오는 것은 불가능하다고 믿게 됐다. 그런데 1736년 스위스의 수학자 오일러가 각 지역을 점으로, 다리를 선으로 표현해 이 사실을 증명했다. 출발 지점으로 돌아오려면 ‘나가는 길’과 ‘돌아오는 길’이 있어야 하므로 짝수개의 선이 연결된 점이 있어야 한다. 그래프에서 네 점 A, B, C, D는 모두 홀수개의 변이 연결돼 있는 꼭지점이다. 따라서 어느 곳에서 출발하더라도 7개의 변을 지나 처음 위치로 돌아올 수 없다.(그림 3)

2. 11개의 전시실이 연결된 전람회장이 있다. 전시실 A에서 관람을 시작해 모든 전시실을 둘러보고 전시실 B에서 끝내려고 한다.(그림 4) 각 통로를 한 번만 지나는 관람방법은 몇 가지가 있을까? 각 전시실을 점으로, 전시실과 전시실을 연결하는 통로를 선으로 표현한 그래프를 그려 관찰하면 전시실 G에서 전시실 K까지 가는 방법은 회전 방향을 잘 고려하면 3×2=6(가지)임을 알 수 있다.(그림 5) 따라서 전시실 A에서 시작해 전시실 B에서 관람을 마치는 방법은 모두 6가지다.

조금 더 생각하기

1859년 아일랜드의 수학자 해밀턴은 같은 크기의 정오각형 12개로 이루어진 정12면체 모양의 퍼즐을 소개했다. 각 꼭지점에 런던 파리 홍콩 뉴욕 등 12개의 도시 이름을 붙였다. 한 도시에서 출발해 다른 도시를 모두 한 번씩 둘러보고 출발한 곳으로 돌아오려면 어떤 길을 선택해야 할까?(그림 6) 이 문제는 상상력을 발휘하면 평면에서도 풀 수 있다. 정12면체의 면을 잡아 늘여 평면 그래프로 만들어 풀면 된다. 굵게 표시한 부분이 가능한 길의 한 예다.(그림 7) 이 길은 각 점을 오직 한 번만 지나 출발점으로 돌아오는데, 해밀턴의 이름을 따서 ‘해밀턴 회로’라고 불린다.