Graphs

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Graph Representation

Adjacency matrix : (u, v)에 edge가 있으면 $A_{uv} = 1$로 채움

    Space proportional : $n^2$

    Checking edge : $\Theta (1)$

    Identifying all edges : $\Theta (n^2)$

 

 

Adjacency List : edge로 연결된 node끼리 list로 연결

    Space proportional  : $n + 2m$

    Checking edge : $O(deg(u))$

    Identifying all edges : $\Theta (m + n)$

 

 

Connected : 모든 pair 사이에 path가 존재할 때, connected라고 한다.

Cycle : 자기 자신으로 돌아오는 path를 cycle이라 한다 ( $v_1, v_2, ... , v_k$ which $v_1 = v_k, k>2$)

 

Tree : Connected이고 Cycle이 없는 Undirected graph

 

Theorem : 다음 3가지 중에 2가지를 만족한다면, 나머지 하나는 자동으로 만족한다.

1. G is connected

2. G does not contain a cycle

3. G has n-1 edges

 

(* 증명은 귀납법으로 증명)

 

 

 

Graph Traversal

Breadth First Search (BFS)

: root s를 기준으로 edge로 연결된 주변 node를 탐색하고, 그 node에서 인접한 node를 탐색하여 search를 넓혀가는 방법

 

 

Properties

BFS runs $O(m+n)$ 

Pf ) 위에서 언급한 Adjacency List 데이터 구조로 구현하면 모든 edge를 탐색하는데 $O(m+n)$의 시간이 걸림

 

BFS로 connected component를 찾을 수 있고, 그 depth가 해당 노드사이의 shortest path이다.

 

 

Testing Bipartiteness

Bipartite Graphs

: Undirected graph에서 각 노드를 red, blue로 모두 칠할 수 있는 graph. 단, 인접한 node는 같은 색깔로 칠할 수 없음

 

* Bipartite graph임이 확보되면 matching의 경우가 줄어들고, independent set 문제를 풀기 쉽기 때문에 그 점에서 이점이 있음

 

 

Lemma 1 : G가 bipartite이면 홀수 길이의 cycle은 존재하지 않는다.

 

Lemma 2 : G가 connected grpah고 layer가 존재할 때,

1. 같은 layer내의 node끼리 edge가 없으면 G는 bipartite이다

2. 같은 layer내에 node끼리 edge가 하나라도 있으면 G는 bipartite가 아니다

 

Pf )

1. 위의 Case(i)에서 각 layer마다 red, blue, red, ... 순으로 색칠하면 됨, 인접한 layer끼리는 연결된 edge가 없음

-> Bipartite

 

2. x, y가 같은 layer이고 z가 x, y의 공통된 조상이라 하자. x-z path와 y-z path의 길이는 같다. 그 길이를 a라 하고 x, y 사이에 edge가 하나 존재하므로, 생기는 cycle의 길이는 2a + 1이다. 이는 홀수개의 edge를 가지는 cycle이므로 Bipartite가 아니다.

 

 

Connectivity in Directed Graphs

mutually reachable : Directed graph에서 u에서 v로 가는 path가 있고, v에서 u로 가는 path가 있을 때strongly connected : graph상의 모든 pair가 mutually reachable할 때

 

Lemma

모든 node가 s로 부터 reachable하고, s가 모든 node로 부터 reachable하면 Strongly connected이다.

 

Pf ) 그래프의 어떠한 node pair에서 s를 거쳐가는 path를 설정하면 됨

 

 

Strong connectivity : Algorithm

1. 그래프 $G$에서 아무 s나 설정하여 s를 기준으로 BFS algorithm 실행

2. s를 기준으로 $G^{rev}$에서 BFS algorithm 실행

3. 두 번의 BFS에서 모두 reachable하다면 G는 Strong connected

 

 

Directed Acyclic Graph & Topological Ordering

DAG : Directed graph이면서 directed cycle이 없는 graph

 

Topological order : edge가 같은 방향을 향하는 순으로 그래프를 ordering한 것

 

 

Topological ordering algorithm

1. incoming edge가 없는 node를 먼저 찾음

2. 그래프에서 해당 node를 삭제하면 그 node가 가르키는 node 기준으로 DAG가 생기므로 recursive로 실행

 

* 위의 알고리즘은 $O(m+n)$  Time complexity 가진다