Graphs

KVV·2024년 11월 13일

알고리즘

E: edge set, V: vertex set 을 가지는 (V,E)의 pair
Edge는 (출발 노드, 도착 노드) 로도 나타낼 수 있다.

Directed graph

방향성을 가진 그래프이다.
$(2,4) \ne (4,2)$

$(2,4)$

Leave from vertex 2 and enters vertex 4
Incident from vertex 2 and to vertex 4

$(2,2)$

Self loop 가 존재

Undirected graph

방향성이 없는 그래프이다.
$(2,4) = (4,2)$

$(2,4)$

Incident on vertex 2 and 4.
Self loop 가 존재하지 않는다.

Graph 용어

1. Adjacency

Edge로 두 vertex가 연결되어 있는가

$(2,4)$

Directed graph
- Not symmetric
- 2 is adjacent to 1.
- 1 is not adjacent to 2.
- $|E| ≤|V|^2$
  - 각 Vertex는 self loop를 포함하여 V개의 edge형성하거나 하지 않을 수 있다.
Undirected graph
- symmetric
- 2 is adjacent to 1.
- 1 is adjacent to 2.
- $|E| ≤\frac{|V|(|V|-1)}{2}$
  - $C(|V|, 2)$

2. Degree

Directed graph
- $Degree =$ $out$ - $degree$ + $in$ - $degree$
- Out-degree: Number of Outgoing edge
- In-degree: Number of Incoming edge
- In-degree 와 out-degree 의 값이 동일하다.
- DAG: Directed Acyclic Graph
Unirected graph
- Out-degree 와 In-degree 가 따로 구별되지 않는다.
- $Degree$ : Number of edges incident on vertex
- Handshaking Lemma
  - G = (V, E) 가 undirected graph 라고 가정하자
  - $\displaystyle\sum_{v∈V}{degree(v)}=2|E|$

3. Path

Vertex를 통과할 때, 지나는 edge의 sequence

<통과 vertex 1, 통과 vertex 2, ...> 으로 표현한다.

Length: Path에서 edge의 개수
Reachable
- 두 vertex간의 path가 존재한다면 reachable 하다고 할 수 있다.
- a is adjacent to b 라면 a is reachable from b라고 할 수 있다.
Simple path: 같은 vertex 를 두 번 이상 방문하지 않는 path

4. Cycle

시작 vertex와 끝 vertex가 동일한 path

Simple cycle: 같은 vertex 를 두 번 이상 방문하지 않는 cycle

Graph 종류

1. Acyclic graph

Cycle이 존재하지 않는 그래프

2. Connected graph

Connected: Undirected graph에서 무작위로 묶은 모든 2개의 vertex pair 간 path가 존재
Connected components: Undirected graph에서 가장 큰 크기의 connected subsets
Strongly connected: Directed graph에서 무작위로 묶은 모든 2개의 vertex pair 가 서로 Reachable
Strongly connected components: Directed graph에서 가장 큰 크기의 strongly connected subsets

3. Complete graph

모든 pair of vertexs 가 adjacent 인 Undirected graph

n개의 vertex가 있을 때, edge의 개수: $\frac{n(n-1)}{2}$

4. Bipartite graph

Graph G = (V, E) 일 때, 각 edge (u,v)에 대해 $u∈V_1$ and $v∈V_2$ / $v∈V_1$ and $u∈V_2$ 을 만족하는 두 집합 $V_1$ , $V_2$ 으로 나뉘어지는 Undirected graph

Forest

Acyclic, undirected graph

Tree

Connected, acyclic, undirected graph

Connected forest
Forest의 connected component는 tree이다.

Tree의 네 가지 성질

모든 두 vertex는 unique simple path로 연결된다.
- Unique: 두 vertex간의 path가 여러 개라면 a - b - a 의 cycle이 생겨 acyclic에 모순이다.
- Simple: Simple이 아니라면 중간에 cycle이 생겨 acyclic에 모순이다.
- Path: Connected이기 때문에 성립한다.
하나의 edge를 제거한 그래프는 Disconnected이다.
- 만약 하나를 제거하고도 여전히 Connected graph 라면 원래의 그래프는 cycle이 존재해야 하는데 이는 Acyclic에 모순이다.
하나의 edge가 추가되면 cycle을 형성하게 된다.
- 어느 두 vertex를 선택하던지 두 vertex간 path가 존재하기 때문에 하나의 edge를 추가하면 cycle이 생긴다.
$|E| = |V| - 1$

Graph representation

1. Adjacency-list representation

Directed graph

나가는 방향에 연결된 vertex 를 모두 저장
Space: $\theta(V) + \theta(E) = \theta(V + E)$

Undirected graph

한 vertex에 연결된 양방향 vertex 를 모두 저장
Space: $\theta(V) + \theta(2E) = \theta(V + E)$

2. Adjacency-matrix representation

Row: 출발, Column: 도착

Directed graph

$i$ 부터 $j$ 로 연결된 edge가 존재하면 $(i, j) = 1$ , 아니라면 $(i, j) = 0$
Space: $∣V∣$ x $∣V∣ = \theta(V^2)$

Undirected graph

$(i, j)$ edge가 존재하면 $(i, j) = 1$
Space: $∣V∣$ x $∣V∣ = \theta(V^2)$
- 특이하게, Undirected graph의 경우 행렬이 대칭적이라 왼쪽 아래 절반 행렬만 사용해도 된다.
Self loop가 없기 때문에 diagonal element = 0 이다.

Transpose of a matrix

$a_{ij}^T = a_{ji}$
Undirected graph의 경우, $A = A^T$ 이다.
$A$ 가 $G$ 의 adjacency matrix라면, $A^T$ 는 $G^T$ 의 adjacency matrix이다.
- $G^T$ : directed graph에서 방향이 반대가 된 graph

Adjacency List vs Adjacency Matrix

G is Sparse
- $∣E∣ < < <∣V∣$
- List is better
  - $∣E∣ < < <∣V∣^2$
  - List: $\theta(V)$
  - Matrix: $\theta(V^2)$
G is Dense
- $∣E∣$ 이 큰 그래프
- Matrix is better
  - $∣V∣ = \frac{V(V-1)}{2}$
  - List: $\theta(V^2)$
  - Matrix: $\theta(V^2)$
  - Matrix가 Linked List에 비해 entry에 걸리는 시간이 적기 때문에 matrix가 더 좋다.
$(i, j)$ 가 존재하는지 테스트하는 경우
- Matrix: $\theta(1)$ time
- List: $\theta(V^2)$
- 따라서 Matrix가 더 좋다.
모든 edge를 탐색
- List: $\theta(V + E)$
  - 전체 Linked list를 한번만 탐색하면 된다.
- Matrix: $\theta(V^2)$
  - 하나의 edge를 탐색할 때마다 전체 matrix를 탐색해야한다.
- 따라서 List의 경우가 효율적이다.