Graph Algorithms (Based on DFS)

Graph review

Graph 

: Graph G는 Vertex (정점) 들의 집합 V(G) , 두 vertex를 이어주는 edge (간선) 들의 집합 E(G) 로 구성되어 있는 구조. G = (V(G), E(G))

Simple graph(라 가정)

: Self-loop 나 multiple edge 를 가지지 않는 graph

 

- Directed graph : E(G) 의 각 원소들은 ordered pair 임 (방향성이 있음)

e = (a,b) (≠(b,a))
- Undirected graph : E(G) 의 각 원소들은 unordered pair 임 (방향성이 없음).

e = {a,b}

 

- (v, u) ∈ E(G) 일 때, v는 u와 adjacent (인접 하다) 
(undirected graph 에서는 u 와 v가 adjacent 하면 v 와 u 도 adjacent 하다) 

- Degree of v (v의 차수, deg (v) ) : G에서 v와 adjacent 한 vertex 수.
- Directed graph 의 경우 in-degree 와 out-degree 를 따로 정의할 수 있다.

 

 

Subgraph (부분 그래프)

- 그래프 G = (V(G), E(G)) 에서 그래프 G의 subgraph G’ = (V’(G), E’(G)) 는 다음과 같은 조건을 만족한다.
i) V’(G) ⊆ V(G) 

ii) E’(G) ⊆ E(G)

이 때, E’(G)의 모든 edge는 V’(G)의 vertex 만을 사용해야 한다 (V’(G) 는 E’(G)에 없는
vertex를 추가적으로 가질 수 있음). ??

 

- Walk (보행) : v 1 , e 1 , v 2 , e 2 ,…, e k , v k 로 이어지는, vertex v 1 , v 2 …와 edge e 1 , e 2 … 가서로 교차되며 나타나는 (alternating) sequence. 이 때 edge e i = (v i , v i+1 ) 이다.
Simple graph 에서 보통 edge 는 생략한다.
- Trail : 같은 edge가 두 번 이상 반복 되지 않는 walk.
- Path (경로) : 같은 vertex가 두 번 이상 반복되지 않는 walk.
- circuit (회로) : 시작 vertex와 마지막 vertex 가 같은 trail

cycle (순환) : 처음 (마지막) vertex를 제외하고 같은 vertex가 두 번 이상 반복되지 않는 circuit

 

 

 

 

 

 

- Reachability and DFS
- Biconnected components
- DFS on directed graphs
- Strongly connected components