그래프의 정의
# 그래프G는 각각 공집합이 아닌 정점의 집합V와 간선의 집합E의 집합이다. 그래프G=(V,E)로 표시한다.
# 정점이란 데이터가 저장되는 노드를 의미한다. 그래프G의 정점들의 집합V는 V(G) = {A,B,C,...}로 표현한다.
# 간선이란 두 정점을 이은 선으로 데이터와 데이터간의 연결을 의미한다. 그래프G의 간선들의 집합E는 E(G) = {(A,B),(A,C),(B,C)...}로 표시한다.
그래프의 분류
1. 방향성 유무에 따른 분류
# 비방향성 그래프(undirected graph) : 간선에 방향이 표시되지 않은 그래프. 간선(A,B)와 간선(B,A)가 서로 같은 간선을 가리킨다.
# 방향성 그래프(directed graph 또는 digraph) : 간선에 방향이 표시된 그래프. 간선(A,B)와 간선(B,A)가 서로 다른 간선을 가리킨다.
# 혼합 그래프(mixed graph) : 비방향성 간선과 방향성 간선을 동시에 가진 그래프.
2. 다중 간선의 존재 유무에 따른 분류
# 단순 그래프(simple graph) : 루프가 존재하지 않고, 정점과 정점을 연결하는 간선이 하나씩만 존재하는 그래프.
# 다중 그래프(multi graph) : 루프가 존재하거나 정점과 정점을 연결하는 간선이 두개 이상인 구간이 존재하는 그래프.
3. 단절된 정점의 유무에 따른 분류
# 연결 그래프(connected graph) : 그래프에 속하는 모든 정점들이 연결되어 있어서 임의의 두 정점 사이에 항상 경로가 존재하는 그래프.
# 단절 그래프(disconnected graph) : 그래프에 단절된 정점이 있어서 임의의 두 정점 사이에 경로가 존재하지 않을수도 있는 그래프.
4. 간선이 가중치를 갖는지에 따른 분류
# 가중치 그래프(weighted graph) : 간선에 따라 서로 다른 가중치를 갖는 그래프.
# 비가중치 그래프 : 간선에 따른 가중치가 없거나 모두 같은 그래프.
5. 그 외
# 완전 그래프(complete graph) : 모든 정점들 사이에 간선이 존재하는 그래프.
# 정규 그래프(regular graph) : 모든 정점의 차수가 동일한 그래프.
# 부분 그래프(subgraph) : 임의의 그래프에서 그래프의 일부분 떼어내서 만든 그래프.
# 물론 그래프G에는 이 외에도 더 많은 부분 그래프가 있다.
그래프 관련 용어
# 인접(adjacent) : 정점A와 간선으로 연결된 정점들을 정점A와 인접한 정점이라고 한다.
# 부속(incident) : 정점A에 연결된 간선들을 정점A에 부속된 간선이라고 한다.
# 경로(path) : 임의의 정점A에서 연결된 간선을 따라 다른 정점C까지 갈 때 거쳐야하는 일련의 정점들의 순서를 정점A에서 정점C까지의 경로라고 한다.
# 순환(cycle) : 정점A에서 출발하여 다시 정점A로 되돌아오는 경로.
# 루프(loop) : 정점A에서 출발하여 다른 정점을 거치지 않고 정점A로 되돌아오는 간선.
# 경로 길이(path length) : 경로상에 포함된 간선의 수를 경로 길이라고 한다.
# 단순 경로(simple path) : 경로상에 포함된 정점들 중 처음과 마지막 정점을 제외한 정점들이 중복되지 않을 때 이 경로를 단순경로라고 한다.
# 단순 방향 경로(simple directed path) : 방향성 그래프에서의 단순 경로를 의미한다.
# 차수(degree) : 정점A에 연결된 가지의 수를 정점A의 차수라고 한다.
# 진입 차수(in-degree) : 방향성 그래프에서 정점A로 들어오는 간선의 수를 정점 A의 진입차수라고 한다.
# 진출 차수(out-degree) : 방향성 그래프에서 정점A에서 나가는 간선의 수를 정점 A의 진출차수라고 한다.
# 연결 요소(connected components) : 비방향성 그래프에서 최대로 연결된 부분 그래프를 연결 요소라고 한다. (위의 부분그래프3은 연결요소가 2개이다.)