Graph Theory

유한개의 정점과 변의 결합양식에 관한 이론이다. 여기서 그래프 (Graph) 는 막대그래프나 2차함수의 그래프와 같이, 양의 변화를 시각적으로 나타낼 때의 그래프가 아니라, 주어진 몇 개의 점(정점)과 그 점을 끝점으로 하는 몇 개의 선(변)으로 이루어진 도형을 말한다 .......... 예를 들어, 철도망이나 도로망의 도형을 머리 속에 그려보자. 거기에는 현실적인 방위나 거리 등은 무시되고, 대폭적으로 생략된 그림이 그려지는 것이 일반적이다. 그럼에도 불구하고, 그 그림이 쓸모가 있는 것은 필요한 정보, 즉 역과 역이 몇 개의 선으로 연결되어 있는가, 바꾸어 타는 것은 어느 역에서 하면 좋은가 하는 것 등이 나타나 있기 때문이다. 또, 회사의 조직도나 가계도, 체육대회 토너먼트의 조합, 전기회로의 배선도 등도 마찬가지이다. 여기서 중요한 것은 점으로 표시되는 것 (각 부서, 부자관계, 대전상대, 저항이나 반도체) 의 결합관계이다 .......... 그래프이론은 이런 질적 관계를 표현하는 연구분야이다. 역사적으로는 스위스의 수학자 Leonhard Euler (1707~83) 가 연구한 ‘쾨니히스베르크의 다리건너기 문제 (Koenigsberg Bridge Problem)’ 가 그 시초이다 ......... 그 후, 영국의 수학자 William Rowan Hamilton (1805~65) 에 의하여 ...... 정십이면체의 각 정점을 세계의 도시로 보고, 각 변은 그 사이를 오가는 여행로로 보았을 경우, 이 여행로를 따라서 각 도시를 단 한 번만 지나가는 세계여행 코스를 찾아내라는 ‘해밀턴의 사이클 문제 (Hamiltonian Cycle Problem)’ 가 제시되었다. 이것은 여행시간이나 여비를 고려한다면 여행업자가 언제나 직면하는 문제이다. 이 정십이면체의 정점이 만드는 그래프는, 평면상의 그래프가 되므로 이 그래프의 각 정점을 한 번씩 지나가는 통로를 생각하면 된다. 이 경우에는 굵은 선으로 된 길이를 구하면 그 통로가 되다. 같은 문제를 임의의 연결 그래프로 생각할 수도 있는데, 이 일반적인 경우의 해답(단숨에 그리기의 정리와 같은)은 얻지 못하고 있다 ..........

순회판매원 문제 (Traveling Salesman Problem) 와 관련된 수학문제는 아일랜드의 수학자 William Rowan Hamilton 와 영국 수학자 Thomas Penyngton Kirkman 에 의해 1800년대에 다루어졌다. 그들의 업적에 대해서는 Graph Theory 1736-1936 에 나와있다.