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

Date: 2022.12.21 Updated: 2022.12.21

카테고리: DataStructure

1. 그래프(Graph)의 정의

그래프는 연결할 객체를 나타내는 정점(Vertex, Node)와 객체를 연결하는 간선(Edge)의 집합으로 구성된다.
그래프 G를 다음과 같이 정의한다. \(G = G(V,E)\)
여기서 V는 정점의 집합(Vertex Set)이고, E는 간선들의 집합(Edge Set)이다.

1) 용어 정리

노드(node): 정점(vertice)라고도 불리며, 일반적으로 노드에는 데이터가 저장됨
간선(edge): 링크, arcs라고도 불리며, 노드간의 관계를 나타냄
인접 정점(adjacent vertex): 간선에 의해 연결된 정점.
단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 위 그래프에서 A의 차수는 3이다.
진출차수(out-degree)/진입차수(in-degree): 방향그래프에서 사용되는 용어
- 진출 차수 는 한 노드에서 외부로 향하는 간선의 수,
- 진입차수 는 외부 노드에서 들어오는 간선의 수

2) 그래프의 특징

그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다.
그래프의 순회는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)으로 할 수 있다.
그래프에는 루트 노드, 부모-자식의 개념은 존재하지 않는다.
트리는 그래프의 한 종류이다.

2. 그래프의 종류

1) 무방향 그래프(Undirected Graph)

무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.

무방향 그래프에서 정점 \(V_i\) 와 \(V_j\) 를 연결하는 간선을 \((V_i,V_j)\) 로 표현하는데, 이 때 두 Vertex의 위치가 바뀌어도 방향이 없기에 동일한 그래프이다.

Figure 1에서
1. \(V(G1)\) = { \(A,B,C,D\) }
2. \(E\) ( \(G1\) ) = { \((A,B), (A,D), (B,C), (B,D), (C,D)\) }

2) 방향 그래프(Directied Graph)

이번엔 두 Vertex를 연결하는 Edge에 방향성이 존재하는 그래프다.

방향 그래프에서 정점 \(V_i\)와 \(V_j\)를 연결하는 간선을 < \(V_i, V_j\) >로 표현하는데, \(V_i\)를 꼬리(tail), \(V_j\)를 머리(head)라고 한다.

In picture
1. < \(V_i, V_j\) >와 < \(V_j, V_i\) >는 서로 다른 간선이다.
2. \(V(G1)\) = { \(A,B,C,D\) }
3. \(E(G1)\) = { < \(A,B\) >, < \(A,D\) >, < \(B,C\) >, < \(C,D\) > }

3) 완전 그래프(Complete Graph)

정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수와 방향 그래프의 최대 간선 수는 다음과 같다.

무방향 최대 간선 수 = \(\frac{n(n-1)}{2}\)
방향 최대 간선 수 = \(n(n-1)\)

4) 부분 그래프(Subgraph)

부분 그래프(Subgraph)는 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프이다.

5) 가중 그래프(Weight Graph)

가중 그래프(Weight Graph)는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프이다.

6) 비순환 방향 그래프(DAG, Directed Acyclic Graph)

방향 그래프 + 사이클이 없는 그래프
트리(Tree)가 여기에 속한다.

7)연결 그래프(Connected Graph)

무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
(이는 무방향 완전 그래프와 동일하다.)

8)단절 그래프(Disconnected Graph)

무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우.

9) 신장 트리(Spanning Tree)

그래프의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프(간선의 수가 제일 적은 그래프)
그래프에서 일부 간선을 채택하여 만든 그래프
- 하나의 그래프에선 여러개의 신장 트리가 나올 수 있음
- 트리의 특수한 형태, 사이클을 포함해선 안된다.

#### (1) 최소 신장 트리(Mininal Spanning Tree, MST)

각 간선에 가중치가 부여되어 있을때, 가중치를 고려하여 최소 비용의 신장트리를 구하는 것
크루스칼, 프림 알고리즘을 이용해서 구할 수 있다.

종류 요약

무방향 VS 방향
가중치
연결 VS 비연결(단절)
사이클 VS 비사이클
완전
신장트리

Reference

[자료구조]그래프
[자료구조]그래프(Graph)의 개념 설명

Meaningful