Graph - 그래프 정의 및 특성

- Directed graph (digraph)

- G = (V, E)

- V: vertex들의 집합

- E: V 원소들의 순서쌍 집합

- directed edge (v, w)는 v->w 또는 vw로 나타냄.

 

- Undirected graph

- G = (V, E)

- V: vertex들의 집합

- E: V 원소들의 순서가 없는 쌍 집합

- undirected edge {v, w}는 v-w 또는 vw, wv로 나타냄.

- incident: 간선-정점 간의 연결 관계 / adjacent: 정점-정점 간의 인접 관계

 

- Weighted Graph

- edge에 값이 있는 경우.

- (V, E, W)또는 (V, E)로 나타냄

 

- Graph Representations

- G = (V, E), n = |V|, m = |E|, V = {v1, v2, ..., vn} 이라고 할 때

- Adjacency matrix representation: 인접행렬 표현

- (Array of) adjacency lists representation: 인접리스트 표현

- 수행 시간 비교

  - v.incidentEdge() : vertex v의 incident edges 구하기

    - matrix: O(n) : 해당 행 또는 열을 훑음 -> vertex 수와 같다.

    - list :    O(deg(v)) : 해당 vertex의 edge 수만큼

  - v.isAdjacentTo(w) : v와 w가 인접한지 판별

    - matrix: O(1) : 해당 인덱스에 접근해 바로 확인 가능

    - list:     O(min(deg(v), deg(w)) : v, w 중 리스트 수가 적은 곳을 훑어 확인

 

- 용어 정리

- Subgraph: 그래프 G=(V, E), G’=(V’, E’)이 있을 때, V’⊆V 이고 E’⊆E 라면 G’는 G의 subgraph

- Complete graph: 그래프의 모든 vertex 쌍이 edge를 갖는 그래프(모든 vertex가 adjacent)

- Adjacency relation: 인접 관계. 두 vertex가 edge로 (바로)연결되어 있는 관계.

- Path: vertex v에서 y로 가는 경로가 v-w-z-y일 때, <vw, wz, zy>로 표현됨. 이때 path의 길이=edge 수=3

- Simple path: 포함된 모든 vertex가 다 다른 path.

- reachable: v에서 w로 가는 path가 존재한다면 w는 v로부터 reachable (w is reachable from v via path p).

- Connected: 임의의 vertex 쌍이 reachable일 때 해당 (undirected)그래프는 connected.
                    어느 한 정점에서 다른 정점으로 갈 수 있음 (모든 정점에 해당).

- Strongly Connected: digraph가 connected일 때.

- Cycle: 시작 정점=끝 정점인 nonempty path. self-loop일 때도 cycle.
           (undirected에선 self loop가 없기 때문에 길이가 3 이상이어야 cycle을 정의할 수 있음.)

- Simple cycle: 시작-끝 정점을 제외한 모든 정점이 한번씩만 등장하는 cycle

- Acyclic: (그래프) 사이클이 없는 경우.

- Undirected forest: acyclic이면서 undirected인 그래프

- Free tree (Undirected tree): connected, acyclic, undirected인 그래프

- Rooted tree: root가 존재하는 free tree

- Connected component: G의 connected subgraph 중 최대로 연결된 subgraph.

 

- 특성 정리

- deg(v) = incoming edge 수 + outgoing edge 수

- 그래프 G=(V, E), n=|V|, m=|E|에 대해 Σdeg(v)=2m  (undirected, directed graph 둘 다 만족하는 특성)

- Digraph G에 대해 Σin_deg(v)=m, Σout_deg(v)=m. m<=n(n-1)

- Undirected graph G의 edge 수 m<=n(n-1)/2

  1. G가 connected라면, m>=n-1

  2. G가 tree라면, m=n-1

  3. G가 forest라면, m<=n-1

- Dense graph: m이 O(n2)에 가까울 때

- Sparse graph: m이 O(n)에 가까울 때