자료구조 | 그래프 1

1. 그래프

---

정점(vertex)의 집합 V(G)와 에지(edge)의 집합 E(G)로 정의
에지: 정점과 정점을 잇는 것

• 일반적으로 그래프는 자기 간선(self-edge)를 가지지 못함

• 자기 간선이란 하나의 정점이 tail이자 head인 형태를 말함

1-1. 인접(adjacent)

정점 $u$와 정점 $v$ 사이에 에지 $(u, v)$가 있을 때 $u$와 $v$는 서로 인접한다고 표현

1-2. 경로(path)

• 경로 길이: 에지 개수
• 단순 경로(simple path): 어떤 경로에서 처음과 마지막을 제외하고 모든 정점이 다를 때를 의미
• 사이클(cycle): 단순 경로에서 처음과 마지막 정점이 같은 것

1-3. 차수(degree)

• 무방향 그래프
  • 어떤 정점 v의 차수 d(v)는 정점 v가 부속된 에지 개수
  • 부속되다(incident): 두 정점 사이에 에지가 존재할 때 에지를 정점에 부속되었다고 표현

• 방향 그래프

  • d(v): 진입차수 + 진출 차수

  • 진입차수(in-degree): 정점 v가 head인 경우이며, 정점 v로 들어오는 에지의 개수를 뜻함 → in-d(v)로 표기

  • 진출 차수(out-degree): 정점 v가 tail인 경우이며, 정점 v에서 나가는 에지 개수를 뜻함 → out-d(v)로 표기

2. 그래프의 종류

---

2-1. 무방향 그래프 vs 방향 그래프

• 무방향 그래프(undirected graph)

  • 방향이 없이 연결된 그래프

  • (a, b): 정점 a와 정점 b를 연결하는 간선

  • (a, b)와 (b, a)는 같은 의미

  • 정점의 개수가 $n$개라면 이 그래프의 최대 에지 개수는 $\frac{n(n-1)}{2}$

• 방향 그래프(directed graph)

  • 방향이 있는 그래프

  • <a, b>: 정점 a → 정점 b로 연결되는 간선 (a는 tail, b는 head로 표현)

  • <a, b>와 <b, a>는 다른 의미

  • 정점의 개수가 $n$개라면 이 그래프의 최대 에지 개수는 $n(n-1)$

2-2. 멀티 그래프(multi-graph)

일반적으로 그래프에서는 에지의 중복을 인정하지 않으나, 중복 에지를 인정하는 자료구조를 멀티 그래프라고 한다.

2-3. 연결된 그래프(connected graph)

두 정점 사이에 경로가 있으면 이를 연결되었다고 표현함
연결된 그래프는 임의의 두 정점을 골랐을 때 모든 경우에 연결된 그래프를 뜻함

• 연결 요소(connected component): 정점 집합

2-4. 부분 그래프(subgraph)

$V(G')\subseteq(G)$ 이고 $E(G')\subseteq E(G)$ 이면 그래프$G'$는 그래프$G$의 부분 그래프이다. 즉, 그래프$G'$의 정점과 에지가 그래프$G$에 모두 포함되는 경우 부분 그래프로 볼 수 있다.

2-5. 신장 부분 그래프(spanning subgraph)

$V'=V$ 이고 $E(G')\subseteq E(G)$를 만족하는 그래프

3. 참고 자료

---

[자료구조] 그래프(Graph)란

양태환, 『파이썬으로 배우는 자료 구조 핵심 원리』, 길벗