[자료구조] 그래프의 정의와 종류

그래프란?

---

일상생활에서 그래프

그래프는 문제 또는 구조를 시각적으로 표현하기 위해 널리 사용되는 자료구조이다. 지하철 노선도와 SNS 관계망이 대표적인 그래프 활용 예시이다. 그래프는 어떻게 구성되어 있을까? 그래프는 정점과 간선으로 구성된다. 정점(vertex, node)은 그래프에서 표현하고자 하는 항목을 의미하고, 간선(edge)는 두 정점 사이의 관계를 의미한다. 두 정점이 간선으로 연결되어 있다면 인접(adjacent)하다고 한다.

왼쪽 서울 지하철 노선, 오른쪽 2호선

서울 지하철 노선도를 그래프 관점으로 해석해보면 다음과 같다. 지하철 노선도에서 각 지하철 역은 그래프에서 표현하고자 하는 항목이기에 정점이 된다. 각 정점(지하철 역)을 이어주는 노선은 1호선, 2호선, 3호선.. 이라는 정점 사이의 관계를 형성하기에 그래프의 간선이 된다. 특히, 홍대입구역과 합정역은 2호선으로 연결되어있기에 인접해있다고 표현할 수 있다.

 

그래프를 수식으로 표현

그래프르 수식으로 표현하면 위와 같다. V는 정점들의 집합이고, E는 간선들의 집합이다. E는 그래프 분류에 따라 내용이 크게 달라진다.

그럼 이제 그래프 분류에 대해서 알아보자.

그래프의 분류: 무방향, 방향 / 가중,  비가중 / 부분, 완전

---

왼쪽부터 무방향, 방향, 가중, 비가중, 부분, 완전 그래프의 예시이다.

 

그래프의 종류를 이해할 때는 '그래프 이름' 그대로 이해하는 것이 좋다. 각 그래프를 간단히 설명하면 아래와 같다.

1. 무방향 그래프: 간선에 방향이 없는 그래프

2. 방향 그래프: 간선에 방향이 있는 그래프

3. 가중 그래프: 간선에 가중치가 있는 그래프

4. 비가중 그래프: 간선에 가중치가 없는 그래프

5. 부분 그래프: 어떤 그래프의 일부분인 그래프

6. 완전 그래프: 서로 다른 모든 정점 쌍들이 반드시 하나의 간선으로 연결되어 있는 그래프

 

그래프의 종류는 여러 가지 그래프의 종류가 중복될 수 있다. 예를 들자면, "무방향 가중 완전 그래프"가 될 수도 있다.

또한, 앞서 말했듯이 무방향 그래프와 가중 그래프에 따라 간선을 표현하는 방법과 노드의 차수가 달라진다.

마지막으로, 무방향 그래프와 가중 그래프에 대해서 더 알아보자.

 

무방향 그래프의 간선과 차수

---

무방향 그래프의 해석

먼저 무방향 그래프에서 차수는 한 정점에 인접한 정점의 개수이다. 정점 a의 차수는 2이고 정점 b의 차수는 3이다.

무방향 그래프에서 간선은 인접한 정점들의 쌍으로 나타내야 한다. 위 그림에서 정점 a와 정점 b를 연결하는 간선은 (a,b)로 표현된다.

방향 그래프의 간선과 차수

---

방향 그래프 해석

방향 그래프의 차수는 진입 차수(in-degree), 진출 차수(out-degree)로 구분된다. 예를 들어, 정점 d의 in-degree는 2,  out-degree는 1이다. 방향 그래프의 간선은 정점들의 순서쌍으로 나타내진다. 예를 들어, 정점 a에서 b로 향하는 간선은 <a,b>로 나타내진다.

 

기타) 노드의 차수 예시, 거리 개념

---

무방향, 방향 그래프에 따른 노드의 차수 예시

위의 그림은 무방향 그래프일 때 한 정점의 차수는 한 정점에 인접한 정점의 개수, 방향 그래프일 때는 한 정점의 차수는 진입 차수, 진출 차수로 구분해서 정하는 것을 보여주는 예시이다.

거리

"노드 u, v 사이의 최단 경로에 있는 링크 수"가 거리로 여겨진다.

위의 그림에서는 노드 d,e가 가장 최단 거리고 링크 수가 1이기 때문에 거리는 1이다.