C로 만드는 자료구조 - 여러가지 그래프

dsbook.tistory.com/280 (이전글)

C로 만드는 자료구조 - 그래프(Graph)란?

 이전 글에서 표로 정리한 그래프 종류에 대해 자세히 알아보자

구분	종류	설명
간선의 방향성	무방향 그래프	간선에 방향이 없는 그래프
	방향 그래프	간선에 방향이 있는 그래프
간선의 가중치	가중 그래프	간선에 가중치가 할당된 그래프
구조적 특징	완전 그래프	연결가능한 최대 간선 수를 가진 그래프
	부분 그래프	원래의 그래프에서 일분의 노드나 간선을 제외하여 만든 그래프
	다중 그래프	중복된 간선을 포함하는 그래프

 그래프 종류의 구분은 크게 나누면 간선의 특징과 구조적 특징으로 나눌 수 있고 간선의 특징, 구조적 특징이 합쳐서 나오는 경우도 있다. 이제 각 그래프 들을 자세히 알아보자 

1. 간선의 특성에 따른 그래프의 종류

 간선의 방향성과 간선의 가중치 유무에 따라 나뉜다.

1.1 무방향 그래프(Undirected Graph)

 무방향 그래프는 두 노드를 연결하는 간선에 방향이 없는 그래프를 말한다. 만약 각 도시를 연결하는 고속도로와 같이 양쪽 도시를 양방향으로 연결하는 경우를 표현할 때 무방향 그래프를 사용하는 것이 적합하다. 

다음 그림은 6개의 노드와 7개의 간선으로 구성된 무방향 그래프 이다.

위 그림을 다시 식으로 나타내보면 아래와 같다.

그래프 G의 노드 : V(G) ={0,1,2,3,4,5}

그래프 G의 간선: E(G)= {(0,1),(0,2),(1,2),(2,3),(3,4),(3,5),(4,5)}

1.2 방향 그래프(Directed Graph)

 방향 그래프는 두 노드를 연결하는 간선에 방향이 있는 그래프를 말하며 다이그래프(Digraph)라고도 한다. 방향 그래프는 모델링 하려는 시스템이 객체들 사이의 연결관계가 대칭적이지 않을 때 사용된다. 만약 일반 고속도로가 아닌 도시의 도로를 표현하는 경우 한쪽 방향으로만 갈 수 있는 일방 통행인 도로도 있을 것이다. 이런 경우 무방향 그래프 보다는 일방통행 도로를 표현할 수 있는 방향 그래프를 사용하는 것이 유용하다. 

다음 그림은 6개의 노드와 9개의 간선으로 구성된 방향 그래프이다.

위 그림을 다시 식으로 나타내보면 아래와 같다.

그래프 G의 노드 : V(G) ={0,1,2,3,4,5}

그래프 G의 간선: E(G)= {<0,1>,<1,2>,<2,0>,<2,1>,<2,3>,<3,2>,<3,4>,<4,5>,<5,3>}

추가적으로 시작 노드는 꼬리(Tail)라 하고, 종료 노드는 머리(Head)라고 한다. 위 그림에서 0에서 1로 가는 간선에서 0이 꼬리이고 1이 머리가 된다.

1.3 가중 그래프(Weighted Graph)

 가중 그래프는 노드를 연결하는 간선에 가중치(Weight)가 할당된 그래프를 말한다. 즉 노드와 노드를 연결하는 간선에 가중치 속성이 있을 때를 가중치 그래프라 하며, 이러한 가중치는 간선상의 비용 또는 거리 등 여러가지 속성으로 사용가능하다. 예를 들어 도시와 도로의 연결 관계 뿐만 아니라 도로의 거리까지 나타내고 싶다면 가중 그래프를 사용하면 된다.

 이러한 가중 그래프는 무방향/방향 그래프와 같이 사용되기도 한다. 무방향 그래프에 가중치 가 있다면 무방향 가중 그래프(Undirected Weighted Graph)라 하며 방향 그래프에 가중치가 있다면 방향 가중 그래프(Directed Weighted Graph)라 한다. 추가적으로 일반적으로 방향 가중 그래프를 네트워크(Network)라고도 한다.

다음 그림은 무방향 가중 그래프와 방향 가중 그래프를 나타낸 것이다.

 이러한 가중 그래프는 노드사이의 연결 관계 이외에 비용 혹은 거리 등의 추가 속성을 정의할 수 있어 응용 분야가 포괄적인 그래프 모델이라 할 수 있다.

2. 구조적 특성에 따른 그래프의 종류

 지금까지 간선에 따른 그래프의 종류를 살펴보았다. 이번에는 그래프의 구조적 특성에 따라 몇 가지 그래프를 살펴보도록 하자.

2.1 완전 그래프(Complete Graph)

 완전 그래프는 그래프 내의 모든 노드가 1:1 간선으로 연결된 경우, 즉 연결 가능한 최대 간선 수를 가진 그래프를 말한다. 앞서 설명한 가중 그래프 때와 마찬가지로 무방향/방향 그래프에 적용가능하다. 노드의 개수를 n ,간선의 개수를 m이라 하였을 때, 무방향 그래프와 방향 그래프에서의 최대 간선 수는 각각 다음과 같이 식으로 정의 할 수 있다.

무방향 그래프 m=n(n-1)/2

방향 그래프 m=n(n-1)

다음 그림은 무방향/방향 완전 그래프를 나타낸것이다.  

노드가 4개인 무방향 완전 그래프의 간선 개수는 4*3/2= 6 이고 방향 완전 그래프의 간선 개수는 4*3=12 개이다. 

2.2 부분 그래프(Sub Graph)

부분 그래프는 원래의 그래프에서 일부 노드나 간선을 제외하여 만든 그래프를 말한다.보통 부분 그래프를 표현할때는 G’라 하면 이는 그래프 G의 부분 그래프 G’라 한다. G’는 G의 노드의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 만들어진 그래프 이며 이를 식으로 나타내면 다음과 같다.

G’ =(V(G’),E(G’))

V(G’) ⊆ V(G)

E(G’) ⊆ E(G)

다음 그림은 그래프 G와 G의 부분 그래프들 몇개를 나타낸 것이다.

2.3 다중 그래프(Multi Graph)

다중 그래프는 중복된 간선을 포함하는 그래프를 말한다.

다음 그림은 다중 그래프를 나타낸다.