백과

그래프 이론에서 말하는 그래프는 기하학적으로 정확한 형식이 있는 것은 아니지만 결절점(結節點：또는 점·꼭지점)과 1쌍의 결절점을 연결하는 선으로 이루어져 있다. 유향(有向) 그래프에서 모든 선은 방향을 가지며, 도로망, 전기회로망, 탄화수소분자구조, 다면체의 꼭지점과 모서리·명령계통·가계도(家系圖) 등은 그래프나 유향 그래프로 나타낼 수 있다.

행정지도와 관계있는 2가지 그래프 가운데 하나는 경계선을 나타내는 그래프이고, 다른 하나는 각 지역에 결절점을 찍고 경계선으로 나눈 각각 1쌍의 결절점을 연결한 그래프이다.

1735년 스위스의 수학자 레온하르트 오일러는 옛날부터 전해오던 쾨니히스베르크 다리에 대한 수수께끼를 분석·발표했다. 이 수수께끼는 섬을 가운데 두고 양 옆으로 갈라져 흐르는 강에 놓인 7개의 다리를 1번씩만 건너서 모든 다리를 건너는 방법을 알아내는 것이다. 그는 이 수수께끼의 답이 존재하지 않음을 증명했고, 이 문제를 가능한 모든 회로망에 일반화시켜 오늘날의 그래프 이론과 위상기하학(位相機何學)이 나오게 되었다.

그래프 채색이란 연결된 결절점들을 서로 다른 색으로 칠하는 방법으로서, 이 방법을 이용하여 시간표를 짤 수 있다. 예를 들어 학생과 교사들이 수업시간표를 짤 때 수업시간을 결절점으로 표시하고, 똑같은 교사나 학생이 그 시간에 있을 경우 두 결절점을 연결하여 색칠하면 시간표를 겹치지 않게 짤 수 있다. 이 경우 색깔은 시간표를 나타낸다.