그래프 이론
그래프 이론
  • 김장천
  • 승인 2010.05.06 15:56
  • 댓글 0
이 기사를 공유합니다

쾨니히스베르크의 다리 문제는 프로이센의 쾨니히스베르크(지금의 러시아 칼리닌그라드)에 있는 7개의 다리에 관련된 문제이다. 쾨니히스베르크에는 프레겔 강이 흐르고 있고, 이 강의 안에는 여의도와 같은 두개의 큰 섬이 있다. 그리고 이 섬들과 도시의 나머지 부분을 연결하는 7개의 다리가 있는데, 이때 7개의 다리들을 한 번만 건너면서 처음 시작한 위치로 돌아오는 길이 있는가 하는 것이 문제이다. 당시 사람들은 수많은 실제 경험을 통해 7개의 다리를 모두 건너 제자리로 돌아오는 것은 불가능하다고 믿게 됐다. 그런데 1736년 스위스의 수학자인 오일러가 각 지역을 점으로, 다리를 선으로 표현해 이 사실을 증명했다. 이것이 유명한 한 붓 그리기의 연구시작이다. 그는 출발 지점으로 돌아오려면 나가는 길과 돌아오는 길이 있어야 하므로 짝수개의 선이 연결된 점이 있어야 한다고 생각했다. 그래프에서 네 점 A, B, C, D는 모두 홀수개의 변이 연결돼 있는 꼭지점이 된다. 따라서 어느 곳에서 출발하더라도 7개의 변을 지나 처음 위치로 돌아올 수 없다는 것이 그의 주장이다. 결국 이 문제를 발전시켜 새로운 수학의 한 분야가 된 것이 그래프이론이다. 실제로, 그래프 이론을 만드는 몇 가지 실례를 들어 이해를 돕고자 한다.

첫 번째 예는, 지하철과 역에 관한 문제이다. 우리들은 지하철 차량 벽에 그려진 지하철 노선도를 보면, 역과 역의 연결 상태를 한눈에 파악할 수 있어 참으로 편리하다. 지도상에는 각 역을 점으로 표현하고, 역과 역을 선으로 연결하고 있다. 점과 선을 이용하여 중요한 정보를 전달하고 있는 셈이다. 수학에선 점과 선으로 그려진 그림을 그래프라고 한다. 특히 그래프의 점은 꼭지점이라 하고, 그래프의 선을 변이라 하며, 한 꼭지점에 연결된 변의 개수를 그 꼭지점의 차수라고 한다. 예를 들면, 지하철 노선도에서 서울역은 차수가 4인 꼭지점이다.

두 번째 예는 유명한 해밀턴 회로 문제이다. 1859년 아일랜드의 수학자 해밀턴은 같은 크기의 정오각형 12개로 이루어진 정12면체 모양의 퍼즐을 소개했다. 이 정 12면체의 각 꼭지점에는 런던, 파리, 홍콩, 뉴욕, 등과 같은 12개의 도시 이름을 붙였다. 그리고 한 도시에서 출발해 다른 도시를 모두 한 번씩 둘러보고 출발한 곳으로 돌아오려면 어떤 길을 선택해야 할까? 하는 것이 문제이다. 물론 한번 방문한 도시는 다시 방문하는 비경제적인 여행은 제외한다는 단서를 붙인다. 이 문제는 상상력을 발휘하면 평면에서도 풀 수 있다. 이 문제는 정12면체의 면을 잡아 늘여 평면 그래프로 만들어 풀면 된다. 이 길은 각 점을 오직 한 번만 지나 출발점으로 돌아오는데, 이것을 해밀턴의 이름을 따서 해밀턴 회로라고 불린다.

근대수학의 아버지로 불리는 수학자 힐베르트는 쾨니히스베르크 출생으로 현대수학의 여러 분야를 창시하여 크게 발전시켰다. 그는 쾨니히스베르크대학을 졸업한 뒤 이 대학의 강사를 거쳐 1893년 교수가 되었다. 1895년 괴팅겐대학으로 옮겨, 후르비츠, 민코프스키와 함께 괴팅겐대학을 세계 수학의 중심지로 만들었다. 힐베르트의 학풍을 찾아 우수한 수학자들이 많이 모여들었다. 만년에는 나치스의 박해를 받았지만 전혀 굽히지 않았고, 괴팅겐에서 죽었다. 그의 업적은 수학의 거의 모든 부문에 미치고 있으나, 특히 대수적 정수론의 연구, 불변식론의 연구, 기하학의 기초 확립, 수학의 과제로서의 몇몇 문제의 제시, 적분방정식론의 연구와 힐베르트공간론의 창설, 공리주의수학기초론의 전개 등을 들 수 있다.

특히 그의 저서 기하학의 기초(1899)에서 제시한 공리계에 의한 기하학의 이론 구성 문제는 그가 1900년 파리에서 개최된 제1차 세계수학자회의(ICM)에서 행한 ‘수학의 전망에 관한 강연’과 더불어 한 세기동안 풀어야 할 문제 23개와 함께 수학에서의 공리주의의 방향을 자리를 잡게 함으로써, 새로운 시대를 열어 준 획기적인 것이다. 100년이 지난후 2000년에는 그가 제시했던 문제는 거의 해결되었고, 포앙카레 추측은 러시아의 기이한 수학자인 기리샤 페럴만에 의해서 3차원 다양체상의 서저리를 갖는 리치 플로 라는 논문으로 2003년 3월에 이 문제를 해결하였다.

댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.