그래프 알고리즘은 수학자 ‘오일러(Euler)’에 의해 고안되었다. 오일런는 1736년도에 ‘쾨니히스베르크의 다리 문제’를 풀기 위해서 그래프 이론을 사용하였다고 한다.
“모든 다리를 한 번씩만 건너서 처음 출발했던 장소로 돌아올 수 있는가?”
이것이 가능하기 위한 필요충분 조건이 다음과 같은데:
“정점 별로 연결된 간선의 수가 모두 짝수이어야, 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다.”
정점 - node
간선 - edge, line, link
‘무방향 그래프 (undirected graph)’ - 방향성이 없는 그래프
‘방향 그래프 (directed graph) or 다이그래프 (digraph)’ - 방향정보가 포함된 그래프
완전 그래프 (complete graph) - 각각의 정저에서 다른 모든정점을 연결한 그래프
간선에 가중치 정보를 둔 그래프를 ‘가중치 그래프’라 한다.
‘부분 그래프’는 원 그래프의 일부를 가져온 그래프를 의미한다.
책에는 나와있지 않지만 부분 그래프는 유도 부분 그래프라는 카테고리가 따로있는데 이것은 포함한 정점들의 모든 간선을 포함 그래프를 의미한다.
그래프는 정점과 간선의 집합이다. 따라서 집합의 표기법을 이용해서 표현할 수 있다. 먼저 다음 그림의 무방향 그래프를 집합의 표기법으로 표현해 보겠다.
그래프는 정점과 간선으로 이루어지므로, 다음과 같이 정점의 집합과 간선의 집합으로 나누어서 표현을 한다.