1. 그래프 Graph
연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조
객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다.
2. 그래프 용어 정리
그래프에서 두 정점 V1과 V2를 연결하는 간선 (V1, V2)가 있을 때, 두 정점 V1과 V2를 인접(adjacent)되어 있다고 하고, 간선 (V1, V2)는 정점 V1과 V2에 부속(incident)되어 있다고 한다.
이때 인접(adjacent)은 정점과 정점의 관계이다.
다음과 같은 그래프에서 정점 1과 인접한 정점은 4와 3이고, 정점 1에 부속되어 있는 간선은 (1, 4)와 (1, 3)이다.
[용어 설명용 그림]
2.1. 차수 degree
정점에 부속되어 있는 간선의 수, 즉 한 정점에 인접한 정점의 개수이다.
무방향 그래프
무방향 그래프에서 정점 1의 차수는 2, 정점 3의 차수는 3이다.
방향 그래프
방향 그래프의 정점의 차수 = 진입차수 + 진출 차수진입차수(in-degree) : 정점을 머리로 하는 간선의 수
진출 차수(out-degree) : 정점을 꼬리로 하는 간선의 수
방향 그래프에서 정점 4의 진입차수는 1, 진출차수는 2이다. 따라서 정점 4의 전체 차수는 (진출차수+진입차수) 이므로 3이다.
2.2. 경로 path
그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것, 즉 정점 V1에서 V2까지 간선으로 연결된 정점을 순서대로 나열한 리스트
무방향 그래프에서 정점 1에서 정점 2까지는 1-3-2 경로와 1-3-4-2 경로, 1-4-2 경로, 1-4-3-2 경로가 있다.
2.3. 경로 길이 path length
경로를 구성하는 간선의 수
2.4. 단순 경로 simple path
모두 다른 정점으로 구성된 경로
무방향 그래프에서 정점 1부터 정점 2까지의 경로 1-4-2는 단순경로이고, 경로 1-4-3-1-4-2는 단순경로가 아니다.
2.5. 사이클 cycle
단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
무방향 그래프에서 단순경로 1-3-2-4-1과 방향 그래프에서 단순경로 1-3-1은 사이클이 된다.
2.6. DAG Directed Acyclic Graph
방향 그래프이면서 사이클이 없는 그래프
2.7. 연결 그래프 connected graph
서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 즉 떨어져있는 정점이 없는 그래프
그래프에서 두 정점 V1과 V2까지의 경로가 있으면 정점 V1과 V2가 연결(connected)되었다고 한다.
따라서 트리는 사이클이 없는 연결 그래프라고 할 수 있다.
2.8. 단절 그래프 disconnected graph
연결되지 않은 정점이 있는 그래프
[연결 그래프와 단절 그래프]
3. 그래프의 종류
3.1. 무방향 그래프 undirected graph
두 정점을 연결하는 간선에 방향이 없는 그래프
정점 V1과 정점 V2를 연결하는 간선을 (V1, V2)로 표현한다. (V1, V2)와 (V2, V1)은 같은 간선을 의미한다. (순서가 없음)
3.2. 방향 그래프 directed graph, 다이그래프 digraph
간선에 방향이 있는 그래프
정점 V1에서 정점 V2를 연결하는 간선 즉, V1 -> V2를 <V1, V2>로 표현한다. 이때, V1를 꼬리(tail), V2를 머리(head)라고 한다. <V1, V2>, <V2, V1>은 서로 다른 간선을 의미하므로 표시에 유의해야한다.
3.3. 완전 그래프 complete graph
각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
정점이 n개인 무방향 그래프에서의 최대 간선 수는 n(n-1)/2개이고, 정점이 n개인 방향 그래프는 두 정점에 대해서 방향이 다른 두 개의 간선을 연결할 수 있으므로 최대 간선 수는 n(n-1)개이다.
3.4. 부분 그래프 subgraph
원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프
이때, G2는 G1의 부분그래프이다.
V(G') ⊆ V(G), E(G') ⊆ E(G)
3.5. 가중 그래프 weight graph, 네트워크 network
정점을 연결하는 간선에 가중치(weight)를 할당한 그래프
