d라이브러리

7차 교육과정 시행으로 고등학교 수학 수업에 ‘지각 변동’ 이 일어났다. 학생들이 선택할 수 있는 수학 과목들이 생겨난 것. 이산수학도 그 중 하나다. 이산수학은 미적분학, 확률 통계에 비해 다소 생소하게 들리지만, 실제로 그 쓰임새가 매우 다양하다.

그래프로 풀린 수수께끼
 

18세기 독일 쾨니히스베르크에는 옛날부터 전해 내려오는 수수께끼가 하나 있었다. 쾨니히스베르크에는 시를 가로질러 흐르는 프레겔 강이 있고 그 강에 크네이포프 섬이 있다. 그리고 이 섬과 시를 연결하는 다리가 모두 7개 있다. 사람들은 다리 건너 크네이포프 섬을 산책하면서 과연 같은 다리를 2번 건너지 않고 7개의 다리를 모두 건너 출발점으로 다시 돌아올 수 있는 방법이 없을까 궁금했다.

시민들은 고민 끝에 당대 유명한 수학자였던 레온하르트 오일러에게 문제 해결을 부탁했다. 오일러는 간단한 그림을 그리더니 사람들이 그토록 고민하던 문제를 너무나 쉽게 풀었다. 그는 우선 프레겔 강에 의해 생긴 두 섬과 두 지역을 점으로 나타냈다. 이어서 그는 다리 수만큼 점들을 연결했다. 4개의 점과 7개의 선으로 이루어진 그림이 만들어졌다.

오일러가 그린 이런 그림을 그래프라고 부른다. 그는 1736년 어떤 점에서 출발해 선을 한번씩만 지나서 다시 그 점으로 돌아올 수 있는 그래프는 각 점에 결합된 선분의 수가 모두 짝수인 성질이 있다는 내용을 증명했다. 이는 흔히 ‘쾨니히스베르크 다리 문제에 대한 해답’으로 불린다.

그는 쾨니히스베르크의 수수께끼의 경우 각 점에서 만나는 선분의 개수가 모두 홀수여서 이 성질을 만족하지 않기 때문에 7개의 다리를 모두 건너면서도 각 다리를 한번씩만 지나는 것은 불가능하다는 결론을 내렸다.
 

수학 영재 발굴에도 한 몫

오일러의 그래프처럼 점이나 선분, 그리고 자연수 등 원소의 개수를 셀 수 있는 집합에 대해 정의된 학문을 이산수학이라고 부른다. 조합론, 그래프이론, 암호이론, 알고리즘 분석 등이 이산수학에 속한다.

이산수학의 가장 큰 특징은 특정한 수학적 지식 없이 순수한 수학적 사고를 토대로 해를 산출하는 게 가능하다는 점이다. 때문에 수학경시대회에서는 이산수학 문제가 많이 다뤄지며, 수학 영재를 발굴하고 교육시키는 주요 프로그램으로 각광받고 있다.

예를 들어 미 이산수학 및 이론컴퓨터과학 센터에서는 저명한 수학자들이 고등학생들과 함께 이산수학 분야의 문제를 공동 연구하는 프로그램을 운영한다. 이 프로그램을 거쳐 간 고등학생들은 대학 입학 후 저명 학술지에 논문을 발표하기도 했다.

또 이산수학을 통해 수학영재를 발굴한 인물도 있다. 20세기 최고의 수학자 중 한 명인 헝가리의 파울 에르도쉬는 조합론의 대가였는데, 자신의 연구에 쏟는 열정만큼 수학에 재능 있는 학생들을 발굴하는데 많은 힘을 기울였다.

1960년 어느 날 그는 12세 소년 포사와 함께 점심 식사를 하고 있었다. 그는 포사에게 1과 2n 사이의 정수 중에서 임의로 (n+1)개의 정수를 뽑았을 때 그 중에 최대공약수를 1로 갖는 두개의 정수가 존재함을 증명하라는 매우 까다로운 요구를 했다.

포사는 먹던 것을 멈추고 잠깐 생각하더니 한 문장으로 간단하게 멋들어진 증명을 하는 것이 아닌가. 에르도쉬는 포사의 수학적 재능에 감탄해 그때부터 우편으로 질문을 보내면서 그래프이론과 조합론을 가르치기 시작했다. 이후 포사는 14살에 그래프이론에 대한 첫 논문을 발표하는 ‘천재성’ 을 보였다.

에르도쉬 수 네트워크
 

이산수학은 수학 영재 발굴뿐 아니라 다른 분야에도 널리 활용된다. ‘에르도쉬 수’ (Erdös Number)가 이를 ‘증명’ 한다. 에르도쉬는 1996년 타계할 때까지 1천4백편 이상의 논문을 발표했다. 그의 공저자는 무려 25개국에 걸쳐 4백50여명에 달한다.

에르도쉬 수는 에르도쉬와 공저자의 관계를 나타낸다. 그와 직접 공동 논문을 집필하면 에르도쉬 수가 1이 되고, 그와 공동 논문을 집필한 사람과 공동 논문을 쓴 경우는 에르도쉬 수가 2라는 식이다. 예를 들어 아인슈타인의 에르도쉬 수는 2고, 양자역학의 대가 하이젠베르크의 에르도쉬 수는 4다.

노벨상 수상자의 에르도쉬 수를 살펴봐도 이산수학의 활용 여부를 쉽게 알 수 있다. 1914-2003년까지 약 1백년 동안 노벨상 수상자 중 물리학 분야에서는 42명, 경제학 분야에서는 13명, 화학분야에서는 14명이 에르도쉬 수를 2-8까지 가지고 있다. 또 노벨 의학상 수상자 중 5명의 에르도쉬 수가 3, 7, 8, 10, 11이다.

그렇다면 이산수학이 실생활에서는 어떻게 활용될까. 7월 1일부터 서울 시내버스 노선이 대대적으로 개편된다. 복잡한 교차로의 신호등 주기를 조정해 노선 개편의 효과를 높여 교통 체증을 줄이려고 한다면 이산수학의 도움이 필요하다.

테헤란로와 영동대로가 만나는 삼성역 4거리는 전형적 교통 혼잡 지역이다. 삼성역 4거리의 교통 체증을 최소화하려면 신호등을 어떻게 조작해야 할까? 단 초록색 신호가 최소 10초 이상은 지속돼야 하고 한 신호주기는 60초다.

이 문제는 몇개의 점과 선으로 표시된 간단한 그래프와 부등식으로 해결할 수 있다. 문제 해결의 핵심은 오일러가 쾨니히스베르크의 다리 문제를 해결한 것처럼 삼성역 4거리를 그래프로 나타내는 것이다.

우선 그림 1과 같이 차가 진행하는 방향을 a-f까지 표시해보자. 이제 a-f를 꼭지점으로 생각한다. 여기서 동시에 초록색 신호를 받아도 차의 진행에 문제가 없는 점들을 선분으로 연결한다. 예를 들어 a와 b는 동시에 초록색 신호를 받아도 차의 진행에 문제가 없으므로 두점을 선분으로 연결할 수 있다. 이런 방식으로 a-f를 연결하면 그림 2와 같은 그래프를 그릴 수 있다.



삼성역 사거리 신호 정하기

그림1 차량의 진행방향을 a-f로 표시한다.
그림2 a-f를 꼭지점으로 하고, 동시에 초록색 신호를 받을 수 있는 점들끼리 선으로 연결한다.
그림3 원(맨 안쪽)을 그린 후 a-f를 호로 나타내 시계그림을 그린다.
그림4 (그림 2)와 비교해 c-e 구간이 선으로 연결되지 않은 그림이 나타난다.

초록색 신호 주기 결정에 도움

문제는 신호의 길이를 정하는 것이므로 이 그래프를 다른 그래프로 변형시킨다. 원을 하나 그려 시계라고 생각하면 원의 주기를 60초라고 생각할 수 있다. 이번에는 이 원 주변에 a-f를 호로 나타낸다. 이때 초록색 신호가 들어오는 시간이 겹쳐도 차의 진행에 문제가 없으면 겹치는 부분이 생기도록 그린다. 예를 들어 b와 c는 초록색 신호가 들어오는 시간이 겹치면 차가 충돌하기 때문에 겹치지 않게 그린다. 이런 방식으로 a-f를 그리면 그림 3과 같은 그래프가 나타난다. 이를 수학 용어로 ‘시계그림’ (clock diagram)이라고 부른다.

시계그림을 그리는 이유는 그림 2의 그래프를 좀더 간소화시키기 위해서다. 예를 들어 그림 2에서는 c와 e가 선분으로 연결돼 있지만, 시계그림에서는 서로 떨어져 있어도 무방하다. 즉 c와 e는 초록색 신호가 동시에 들어오지 않아도 문제를 푸는데 영향을 주지 않기 때문에 고려하지 않아도 된다. 시계그림을 그리기에 따라 c와 e, d와 f 모두 겹치지 않게 그릴 수 있다.

이제 시계그림에서 겹치는 원호들을 그래프로 나타내면 그림 4와 같다. 신호 대기시간을 최소로 하는 초록색 신호 주기를 구하기 위해 남아있는 문제는 a-f의 각 경우에 대해 초록색 신호가 들어오는 시간을 임의의 변수로 나타내 연립부등식을 만들고, 그 연립부등식을 풀면 된다.

이런 과정으로 문제를 풀어보면 여러개의 해가 나온다. 우선 초록색 신호 주기를 15초로 줄 수 있다.

테헤란로의 양방향 a와 b에 15초 동안 초록색 신호를 준 다음 영동대로의 c와 d 방향에 15초 동안 초록색 신호를 준다. 이 중 c는 15초 후 빨간색 신호를 주고, 동시에 f에 초록색 신호를 준다. 이번에는 15초 후 d에 빨간색 신호를 주고, e에 초록색 신호를 준다. 15초 후 테헤란로의 양방향 a와 b에 15초 동안 초록색 신호를 주고 위의 과정을 되풀이 한다.

15초 이외에 다른 신호 주기도 가능하다. 테헤란로의 양방향 a와 b에 15초 동안 초록색 신호를 준 다음 영동대로의 c와 d 방향에 18초 동안 초록색 신호를 준다. 이 중 c는 18초 후 빨간색 신호를 주고, 동시에 f에 초록색 신호를 준다. 이번에는 12초 후 d에 빨간색 신호를 주고, e에 초록색 신호를 준다. 15초 후 테헤란로의 양방향 a와 b에 15초 동안 초록색 신호를 주고 위의 과정을 되풀이 한다.

이렇게 몇개의 해 중에서 그 지점의 교통상황에 맞춰 가장 적합한 해를 선택하면 삼성역 4거리 문제는 해결된다. 만약 영동대로의 교통량이 테헤란로보다 더 많다면 c와 d에 초록색 신호를 더 오래주는 두번째 해를 선택하면 된다.