Graph

그래프(graph)는 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)으로 구성된 자료 구조이다. 정점은 노드(node)라고도 한다.

일반적으로 그래프는 각 용어의 영문 앞 글자를 따서 G = (V, E)로 표현한다.
G: Graph(그래프)
V: Vertex(정점)
E: Edge(간선)

그래프의 종류를 알아보기 전에, 그래프 관련 용어들을 먼저 알아두는 것이 좋다.

그래프 관련 용어들

• 인접(adjacent): 두 정점이 간선으로 연결되어 있으면 인접하다고 한다.

• 차수(degree): 정점에 연결된 간선의 수를 나타낸다. 위 녹색 그림에서 정점 5의 차수는 2이며, 아래 회색 그림에서 정점 E의 차수는 3이다.

• 진입 차수(in-degree): 해당 정점으로 향하는 간선의 수를 의미한다. 아래 그림에서 정점 E의 진입 차수는 2이다.

  

• 진출 차수(out-degree): 해당 정점에서 나가는 간선의 수를 의미한다. 위 회색 그림에서 정점 E의 진출 차수는 1이다.

• 경로(path): 한 정점에서 다른 정점으로 이어지는 정점들의 리스트를 뜻한다. 아래 하얀 그림에서 A에서 E로 가는 경로 중 하나는 {A, B, D, E} 이다. A에서 E로 가는 또 다른 경로 중 하나는 {A, B, E} 이다.

  

• 경로 길이(path length): 경로를 구성하는 간선의 개수이다. 위 그림에서 {A, B, D, E} 의 경로 길이는 3이며, {A, B, E} 의 경로 길이는 2이다.

• 단순 경로(simple path): 모두 다른 정점으로 구성된 경로를 의미한다. 경로 {A, B, D, E} 와 경로 {A, B, E} 는 단순 경로이다.

• 사이클(cycle): 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로를 의미한다. 아래 그림에해당하는 {2, 4, 3, 2} 경로를 예로 들 수 있다.

  

그래프 종류

그래프는 간선의 방향성 유무에 따라 무방향 그래프와 방향 그래프로 구분할 수 있다.

1. 무방향 그래프(undirected graph)

무방향 그래프는 간선에 방향성이 없는 그래프이다. 두 정점이 연결되어 있을 때, 순서가 없으므로 위 이미지의 왼쪽 그래프에서 (2, 4) 간선과 (4, 2) 간선은 동일한 간선을 의미한다.

무방향 그래프에서 정점의 개수가 n개 일 때, 최대 간선의 개수는 n x (n-1) / 2 이다.
ex) 정점의 개수 3개 ==> 최대 간선의 개수 = 3 x (3-1) / 2 => 3
ex) 정점의 개수 4개 ==> 최대 간선의 개수 = 4 x (4-1) / 2 => 6
ex) 정점의 개수 5개 ==> 최대 간선의 개수 = 5 x (5-1) / 2 => 10
ex) 정점의 개수 10개 ==> 최대 간선의 개수 = 10 x (10-1) / 2 => 45
ex) 정점의 개수 100개 ==> 최대 간선의 개수 = 100 x (100-1) / 2 => 4,950

아래 그림은 각각 정점의 개수가 4, 5, 6, 7개인 완전 그래프이다. 이는 각 정점에서 이을 수 있는 간선을 전부 이은 것으로, 간선의 개수가 각각 최대 간선의 개수 값인 6, 10, 15, 21 임을 알 수 있다.

2. 방향 그래프(directed graph)

방향 그래프는 간선에 방향이 있는 그래프이다. 두 정점이 연결되어 있을 때, A에서 B로 향하는 간선을 <A, B>로 표기한다. 아래 그림에서 5 정점과 11 정점이 연결되어 있는데, 5 정점에서 11 정점으로 향하기 때문에 간선을 <5, 11>으로 표기할 수 있다. 따라서 <5, 11> 간선과 <11, 5> 간선은 다른 간선을 의미한다.

방향 그래프에서 정점의 개수가 n 일 때, 최대 간선의 개수는 n x (n-1) 이다. 무방향 그래프보다 최대 간선의 개수가 *2 만큼 많은 이유는, 아래 그림과 같이 각 정점 간의 간선에 방향이라는 개념이 추가되었기 때문이다.

3. 그 외의 그래프들

위에서 설명한 그래프 외에도 여러 종류의 그래프가 있다.

* 부분 그래프(sub graph): 기존 그래프에서 일부 정점 또는 간선을 제외한 그래프이다.

* 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프이다.

* 완전 그래프(complete graph): 간선을 최대로 가진 그래프로, 연결 그래프(connected graph) 라고도 한다. 정점의 개수가 n일 때, 무방향 그래프의 간선 수가 n(n-1)/2 이면 완전 그래프이다. 이와 마찬가지로 방향 그래프인 경우 정점의 개수가 n일 때, 간선의 수가 n(n-1) 이면 완전 그래프이다.

* 유향 비순환 그래프(DAG, Diredted Acyclic Graph): 아래 그림과 같이, 방향 그래프이면서 사이클이 없는 그래프를 말한다.

결론

위와 같이 그래프는 정점(vertex)과 간선(edge)으로 구성된 자료구조로, 간선의 방향성에 따라 무방향 그래프와 방향 그래프로 구분되며, 각각 최대 간선 수는 n(n-1)/2 와 n(n-1)개이다. 그래프는 네트워크 구조, 경로 탐색, 관계 모델링, 소셜 네트워크 분석 등 실세계의 연결 관계를 표현하고 해결하는 핵심적인 자료구조로, 알고리즘에서도 필수적인 요소이다.