『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 

본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인 공부 및 복습이 주목적일 뿐, 상업적 의도는 없습니다. 

Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein』

4-1. 그래프

4-1-1. Directed and Undirected

Directed graph(digraph) G는 (V, E)의 쌍으로, V는 유한한 집합이고 E는 V의 이진 관계(binary relation)이다.

집합 V는 G의 vertex set (꼭짓점) 이라고 하고 그 element들은 vertices라고 한다. 

집합 E는 edge set (모서리)라고 하고, element는 edges라고 한다.

그림 (a)는 vertex set {1, 2, 3, 4, 5, 6} 에 대한 directed graph이다. Vertices는 원으로, edge는 화살표로 표현된다.

그림에서처럼 self-roof 또한 가능하다.

Undirected graph G = (V, E) 에서는, E는 unordered pair of vertices다. (특정 방향성 없이 쌍방향)

다시 말해, edge는 집합 {u, v}로, u, v ∈ V 이고, u != v 이다. 

Convention 상으로, edge를 {u, v}가 아닌 (u, v)로 표현하고, (u, v) = (v, u) 이다.

Undirected graph에서 self-loop은 금지되어 있다.

4-1-2. Edge

Directed의 경우, edge (u, v)는 incident from u, incident to v 혹은 leaves u and enters v라고 한다.

반면 undirected에서는 edge (u, v)를 incident on u와 v 라고 한다.

예를 들어 그림 (b)에서 edges incident on vertex 2는 (1, 2)와 (2, 5)다.

만약 (u, v)가 그래프 G = (V, E)의 edge면, vertex v는 vertex u에서 adjacent라고 한다.

Undirected 경우 adjacency relation은 symmetric이지만,

Directed의 경우 그림 (a)에서 vertex 2 is adjacent to vertex 1이지만, 반대는 아니다. 1 → 2 로 표현한다.

4-1-3. Degree

Undirected 그래프에서 vertex의 degree는 거기에 incident한 edge 수로 결정된다.

그림 (b)에서 vertex 2의 degree는 2다. Degree 0인 vertex 4는 isolated라고 한다.

Directed 그래프에서 vertex의 out-degree는 leaving하는 edge의 수, in-degree는 들어오는 edge의 수를 말한다.

그 vertex의 degree는 in-degree와 out-degree를 합한 수이다.  

그림 (a)의 vertex 2는 in-degree 2, out-degree 3, 그리고 degree 5를 가진다.

4-1-4. Path

어떤 그래프 G = (V, E)에서 path of length k from a vertex u to a vertex u' 는, v에서 u까지 k개의 edge를 거쳐가는 길을 말한다.

u에서 u'까지 path p가 존재하면, u' is reachable from u via p라고 하고, directed의 경우 로 적기도 한다.

어떤 path의 모든 vertices들이 distinct면 simple path라고 한다.

어떤 path p = <v0, v1, ..., vk>의 subpath는 그 vertices들의 contiguous subsequence다.

즉, 0≤i≤j≤k에 대해, subsequence of vertices <vi, vi+1, ..., vj)는 p의 subpath다.

4-1-5. Cycle

Directed graph의 path <v0, v1, ..., vk> 가 v0 = vk이고 최소한 1개의 edge를 포함한다면, cycle을 형성한다고 한다.

그리고 v1, v2, ..., vk가 distinct하면 simple cycle이라 한다. self-loop은 length 1인 cycle이다.

path <v0, v1, ..., vk-1, v0>와 path <v0', v1', ..., vk-1', v0'>에 대해 어떤 정수 j가 v_i' = v_{(i+j)mod k} 를 만족하면 same cycle이라고 한다.

<1, 2, 4, 1>은 <2, 4, 1, 2>와 <4, 1, 2, 4>와 같은 cycle이다.

<2, 2>의 self-loop는 cycle이고, self-loop이 없는 directed graph는 simple이라고 한다. 

Undirected의 경우, k >= 3이고 v0 = vk일 때 path <v0, v1, ..., vk>는 cycle을 형성한다고 한다.

각 v1, ..., vk가 distinct면 simple하다고 한다. 

Cycle이 없는 그래프의 경우 acyclic이라 한다.

4-1-6. Connect

Undirected graph의 경우, 모든 vertex이 모든 다른 vertex로부터 reachable하면 connected라고 한다.

Connected components는 각각 연결된 vertices를 말한다. 그림 (b)는 {1, 2, 5}, {3, 6}, {4} 세 개의 connected components를 가졌다.

단 하나의 connected component를 가진 undirected graph를 connected라고 한다.

Directed graph의 경우, 모든 두 vertices가 서로에게 reachable하면 strongly connected라고 한다.

Strongly connected components는 상호 reachable란 vertices들을 말한다. 

그림 (b)는 {1, 2, 4, 5}, {3}, {6} 세 개의 strongly connected components를 가졌다. 3과 6은 상호 연결이 되지 않아 component를 형성하지 못한다.

4-1-7. Isomorphic

어떤 두 그래프 G = (V, E)와 G' = (V', E')가 (u, v) ∈ E iff (f(u), f(v)) ∈ E'의 일대일 bijection V → V' 가 존재하면 isomorphic이라 한다.

다시 말해, G의 vertices들을 relabel해서 G'의 vertices로 만들면서 corresponding edges를 유지할 수 있다는 것이다.

그림 (a)는 isomorphic한 반면, (b)는 G는 degree 4인 vertex가 있는 반면 G'는 없어서 isomorphic하지 않다.

4-1-8. Subgraph

G' = (V', E')와 G = (V, E)에서, V' ⊆ V이고 E' ⊆ E 이면 G'는 G의 subgraph라고 한다.

어떤 V' ⊆ V가 주어지면, subgraph of G induced by V'는 E' = {(u, v) ∈ E: u, v ∈ V'} 로 얻은 그래프 G' = (V', E')이다.

Subgraph induced by 그림(a)의 vertex set {1, 2, 3, 6}는 그림(c)의 edge set {(1, 2), (2, 2), (6, 3)}이다.

4-1-9. Version

어떤 undirected graph G = (V, E)의 directed version은 G' = (V, E'), where (u, v) ∈ E' iff (u, v) ∈ E 이다.

다시 말해 우리는 각 undirected edge (u, v)를 두 개의 directed edges (u, v)와 (v, u)로 대체한다.

어떤 directed graph G = (V, E)의 undirected version은 G' = (V, E'), where (u, v) ∈ E' iff u != v and (u, v) ∈ E이다.

즉, undirected version은 self-loop을 제거하고 방향성을 제거한 버전이다.

Directed graph에서 vertex u의 neighbor는, undirected version에서 adjacent한 vertex를 말한다.

즉, u != v이고 (u, v) ∈ E거나 (v, u) ∈ E면 v는 u의 neighbor라고 한다.

Undirected graph에서는 adjacent하면 neighbor라 한다.

4-1-10. Names

모든 쌍의 vertices가 adjacent한 undirected graph를 complete graph라 한다.

어떤 undirected graph G = (V, E)를 두 집합 V₁, V₂로 나눠, (u, v) ∈ E implies either (u ∈ V₁ and v ∈ V₂) or (u ∈ V₂ and v ∈ V₁)면 bipartite graph라 한다.

즉, 모든 edge들이 두 집합 사이에만 연결되어 있는 것이다.

Acyclic한 undirected graph는 forest라 하고, connected, acyclical, undirected graph는 (free) tree라 한다.

Directed acyclical graph는 첫글자를 따 dag라고 한다.

Multigraph는 undirected graph와 비슷하지만, 두 vertices 사이 복수의 edge를 가질 수 있고 self-loop도 허용된다.

Hypergraph는 undirected graph와 비슷하지만, 각 hyperedge는 두개의 vertices가 아닌, arbitrary subset of vertices를 연결한다.

Contraction of undirected graph G = (V, E) by edge e = (u, v)는 새로운 그래프 G' = (V', E') where V' = V - {u, v} U {x} and x is a new vertex다.

새로운 edge 집합 E'는 E에서 edge (u, v)를 제거하고, 각 vertex w incident on u or v에 대해 (u, w) 혹은 (v, w)중 E에 속한 것을 제거하고 새로운 edge (x, w)를 더함으로서 형성한다.

그럼으로써 u와 v는 single vertex x로 contract 된다.

4-2. Trees

4-2-1. 정의

Connected, acyclic, undirected graph를 (free) tree라고 한다. 

Disconnected, acyclic, undirecte graph는 forest라고 한다.

그림 (a)는 tree, (b)는 forest, (c)는 cycle을 포함하므로 아무것도 아니다.

G = (V, E)가 undirected graph면, 아래의 statement들은 모두 동일하다.

1. G는 free tree다.

2. G의 어떤 두 vertices들은 unique simple path로 connect되어 있다.

3. G는 connected지만, E에서 그 어떠한 edge가 제거되어도 disconnected로 된다.

4. G는 connected고, |E| = |V| - 1이다.

5. G는 acyclic이고, |E| = |V| - 1이다.

6. G는 acyclic이지만, 아무 edge가 E에 추가되어도, graph는 cycle을 가지게 된다.

4-2-2. Rooted and Ordered Trees

Rooted tree는 vertices 중에 하나가 다른 것과 차별되는 free tree를 말한다. 

그 특정한 vertex를 root라 하고, rooted tree의 vertices는 node라 한다.

그림 (a)는 node 12개를 가지고 root가 7인 rooted tree를 보여준다.

Tree T의 root가 r일 때, 어떤 node x가 있다 하자. r에서 x까지의 unique simple path에 있는 node y들을 x의 ancestor라 하고, x는 descendant라 한다.

y가 x의 ancestor고 y != x면, y와 x는 각각 proper ancestor, proper descendant라 한다. 

Subtree rooted at x는 x에 root된, x의 descendant들로 induce 된 tree를 말한다.

예를 들어 그림 (a)에서 subtree rooted at node 8은, node 8, 6, 5, 9를 포함한다.

바로 위의 ancestor를 parent라 하고, 반대는 child라 하며, root는 T에서 유일하게 parent가 없다.

두개의 node가 공통의 parent를 가지면 그들은 siblings라 한다. 

children이 없는 node는 leaf 혹은 external node라 부른다. Nonleaf node는 internal node다.

Rooted tree T에서 node x의 children의 숫자는 x의 degree라고 한다. 

Root r에서 node x까지 simple path의 length는 depth of x in T라고 한다.

Tree의 level은 동일한 depth의 모든 node로 구성된다.

어떤 node의 height는 그 node에서 leaf까지의 longest simple downward path의 edge 개수를 말하고, tree의 height는 root의 height이다.

Tree의 height는 또한 node 중 largest depth와 동일하다.

Ordered tree는 각 node의 children이 ordered된 rooted tree를 말한다.

그림 (a)와 (b)는 rooted tree로서는 동일하지만, ordered tree로서는 다르다.

4-2-3. Binary and Positional Trees

Binary tree는 recursively 정의하면, 어떤 유한한 node 집합에 대해, 1) node가 없거나, 2) 세 개의 disjoint set of nodes: root node, left subtree, right subtree로 정의된다.

Node가 없는 binary tree는 empty tree 혹은 null tree라고 하고, 어떤 때는 NIL로 표기한다.

만약 left subtree가 nonempty면, 그 subtree의 root는 전체 tree의 root의 left child라고 한다. (right child도 마찬가지)

만약 subtree가 NIL이면, child가 absent 혹은 missing이라고 한다.

그림 (a)는 binary tree, (b)는 ordered tree로서는 (a)와 같지만 node 7의 left child가 right child가 되어 binary tree로서는 다르다.

(c)의 경우 모든 missing child를 children이 없는 node로 대체하여 사각으로 표기하였고, 이를 full binary tree라 하며, 각 node는 leaf이거나 degree가 정확히 2다.

Positional tree에서는, node의 children이 distinct positive integers로 표기된다. 정수 i로 표기된 child가 없으면 그 node의 ith child는 absent이라 한다.

k-ary tree는 각 node에 대해 k보다 큰 label의 children들이 모두 missing한 positional tree를 말한다. 즉, binary tree는 k = 2인 k-ary tree이다.

Complete k-ary tree는 모든 leaves가 같은 depth이고 모든 internal nodes가 degree k를 가진 k-ary tree를 말한다.

아래 그림은 height 3의 complete binary tree를 보여준다.

Complete k-ary tree에서는 각 depth h마다 k^h의 children을 가진고, 따라서 n leaves를 가진 complete k-ary tree의 height는 log_kn이다.

그리고 internal node의 숫자는 

이며, 따라서 complete binary tree는 2^h - 1 internal node를 가진다.

4-3. Graph Algorithms

Graph G = (V, E)를 표현하는 방식은 collection of adjacency list와 adjacency matrix 두 가지가 있다.

일반적으로 adjacency-list 표현이 sparse graph(edge개수 |E|가 vertices 개수 |V|²보다 훨씬 적은)을 표현하는 compact 방법을 제공하기에 많이 사용된다.

이 섹션에서는 거의 adjacency-list 표현을 쓰지만, 만약 그래프가 dense(|E|가 |V|²에 가까운)할 경우나 두 given vertices를 잇는 edge가 존재하는지 빨리 알아야할 때는 adjacency-matrix 표현을 쓴다.

(a)는 undirected graph, (b)는 adjacency-list 표현, (c)는 adjacency-matrix 표현이다.

(a)는 directed graph, (b)는 adjacency-list 표현, (c)는 adjacency-matrix 표현이다.

Adjacency-list의 경우 각 vertex별로 행이 있고, 그 vertex와 adjacent한 edge를 나열한다. Pseudocode에서 array Adj를 edge set E와 마찬가지로 graph의 attribute로 취급한다.

Directed graph의 경우 모든 adjacency list의 length의 sum은 |E|이고, undirected의 경우 2|E|이다.

Adjacency-list 표현의 경우 Directed와 undirected graph 둘다 required memory가 θ(V + E)라서 좋다.

또한 weighted graph를 표현할 때, weight function w: E → R을 이용해 간단히 w(u, v)를 저장하면 된다.

그러나 한 가지 단점은, 어떤 edge (u, v)가 존재하는지를 알려면 adjacency list Adj[u]에서 v를 찾는 수밖에 없다는 것이다.

Adjacency-matrix 표현은 이 단점을 보완하지만, edge의 수와 상관없이 많은 |V| x |V| matrix의 θ(V²) 메모리를 필요로 한다.

Adjacency-matrix는 a_ij = 1 if (i, j) ∈ E 이고, 0 otherwise로 표현된다.

Undirected graph의 경우 대각으로 symmetric하다. 따라서 어떤 application에서는 upper diagonal만 저장해서 메모리를 절반으로 줄이기도 한다.

Adjacency-matrix에서도 weighted graph의 경우 edge (u, v) ∈ E의 weight w(u, v)를 저장하면 된다.

Adjacency-list가 matrix보다 space가 효율적이지만, matrix가 더 간단하므로 graph가 크지 않을 때는 matrix를 선호한다. 

또한 unweighted graph 경우 matrix에서는 entry당 1비트만 들어가는 장점이 있다.

Graph의 대부분 알고리즘들은 vertices와 edges에 attribute을 포함할 필요가 있다. 

이 경우, 평상적인 notation을 사용한다. vertex v의 attribute d는 v.d, edge (u, v)의 attribute f는 (u, v).f 로 표기한다.

실제 프로그램상에서 이런 attribute를 저장하고 구현하는데는 언어별로, 알고리즘별로, 그래프 사용 용도별로 다르다.

4-4. Queues

Stack와 queue는 DELETE operation으로 제거되는 element가 prespecified된 dynamic set다.

Stack의 경우 LIFO이고 queue의 경우 FIFO(first-in, first-out)이다.

Queue에의 INSERT operation을 ENQUEUE, DELETE operation을 DEQUEUE라고 한다.

Queue는 head와 tail이 있고, 어떤 element가 enqueue되면 tail부터, dequeue되면 head에서 실행된다.

어떤 array Q[1, ..., n]에서 Q.head는 첫번째 index, Q.tail은 마지막 index의 다음 element, 즉 새로운 element가 삽입될 장소를 지정한다.

만약 Q.head = Q.tail이면 queue는 empty이고, 초기에 Q.head = Q.tail = 1 이며, 여기에 dequeue를 하려하면 queue underflow가 발생한다.

만약 Q.head = Q.tail + 1이면, queue는 full이고, 여기에 enqueue를 하려들면 queue overflow가 발생한다.

아래의 pseudocode는 n = Q.length임을 가정한다.

그림에서처럼 location n 다음은 location 1이다.

ENQUEUE(Q, x)

1 Q[Q.tail] = x

2 if Q.tail == Q.length

3 Q.tail = 1

4 else Q.tail = Q.tail + 1

DEQUEUE(Q)

1 x = Q[Q.head]

2 if Q.head == Q.length

3 Q.head = 1

4 else Q.head = Q.head + 1

5 return x

위의 operation들은 둘다 O(1) 시간이 걸린다.

4-5. Breadth-first search

4-5-1. 정의

Breadth-first search는 그래프를 검색하는데 가장 간단한 알고리즘이다.

그래프 G = (V, E)와 source vertex s에 대해, s에서 reachable한 모든 vertex와 거기까지의 거리를 찾는다.

이 알고리즘은 directed와 undirected 둘 다에서 적용된다.

BFS의 이름은, 그것이 discovered와 undiscovered vertices의 frontier에 uniformly expand하기 때문이다.

다시 말해, s로부터 distance k에 있는 모든 vertices를 찾은 후에야 distance k+1의 vertices를 찾는다.

그 과정에서 BFS는 각 vertex를 흰색, 회색, 검정으로 색칠한다. 

모든 vertices는 흰색으로 시작되어, 발견되면 회색 혹은 검정으로 변한다.

회색은 frontier를 말하고, 검정은 이미 discover되고 adjacent도 회색/검정인 vertices를 말한다.

BFS는 breadth-first tree를 생성하는데, 초기에는 root인 source vertex s만 갖고 있다.

이미 발견한 vertex u의 adjacency list에서 새로운 흰색 vertex v를 찾을 때마다, vertex v와 edge (u, v)는 tree에 추가된다.

이때 u는 v의 predecessor 혹은 parent라고 한다. Vertex는 최대 한 번 발견되기에, 최대 1개의 parent를 가진다. Ancestor/descendant 관계도 tree와 마찬가지로 적용된다.

아래의 BFS는 input graph G가 adjacency list를 사용해 표현된다 가정한다. 그리고 몇몇 추가적인 attribute들을 각 vertex에 붙인다.

각 vertex u ∈ V의 색을 u.color에 저장하고, u의 predecessor를 u.π에 추가한다. 만약 predecessor가 없으면 u.π = NIL이다.

u.d는 s에서 u까지의 거리를 저장한다. 또한 알고리즘은 회색 vertices를 관리하기 위해 FIFO queue Q를 사용한다.

4-5-2. Pseudocode와 Running Time

초기화 이후에, BFS는 어떤 vertex를 흰색으로 만드는 일은 절대 없다. 

따라서 line 13의 test는 각 vertex가 최대 한 번만 enqueue/dequeue될 것을 확실시 한다. 

Enqueue/dequeue는 O(1) 시간이 걸리므로, queue operation에 드는 총 시간은 O(V)이다.

또한 이 프로시져는 각 vertex의 adjacency list를 해당 vertex가 dequeue되었을 때만 스캔하므로, 각 adjacency list를 한 번만 스캔한다.

모든 adjacency list의 길이의 합은 θ(E)이므로, adjacency list를 스캔하는데 걸리는 시간은 O(E)이다. 

초기화에 걸리는 코스트는 O(V)이고, 따라서 BFS에 드는 모든 running time 총합은 O(V + E)이다.

고로, BFS는 그래프 G의 adjacency-list 표현과 linear하게 시간이 걸린다.

4-5-3. Shortest Paths

Shortest-path distance δ(s, v)는, s에서 v까지의 최소한으로 필요한 edge 개수이다. 

s에서 v까지 path 자체가 없으면, δ(s, v) = ∞이다.

BFS가 정확하게 shortest-path distance를 측정하는지 확인하기 전에, shortest-path distances의 중요한 특성을 알아보자.

첫째(Lemma), 그래프 G = (V, E)가 directed 혹은 undirected이고, s ∈ V 가 임의의 vertex라 하자.

그러면 아무 edge (u, v) ∈ E에 대해, δ(s, v) ≤ δ(s, u) + 1 이다.

둘째(Lemma), 그래프 G = (V, E)가 directed 혹은 undirected이고, BFS가 source s ∈ V에서 실행된다 하자.

그러면 종료시 BFS에 의해 계산된 각 vertex v ∈ V의 값 v.d는 v.d ≥ δ(s, v)를 만족한다.

셋째(Lemma), 그래프 G = (V, E)에 대해 BFS가 실행될 때 queue Q가 vertices <v₁, v₂, ..., v_r>을 포함하고, v₁이 head, v_r이 tail이라 하자.

그러면 i = 1, 2, ..., r-1에 대해 v_r.d ≤ v₁.d + 1 AND v_i.d ≤ v_i+1.d 이다.

넷째(Corollary), vertices v_i, v_j가 BFS 실행 중 enqueue되었다 하고, v_i가 v_j보다 먼저 enqueue되었다 하자.

그러면 v_j가 enqueue되는 시점에 v_i.d ≤ v_j.d 이다.

이제 BFS가 shortest-path distance를 정확히 찾는다고 증명하자. 

(Theorem) 그래프 G = (V, E)가 directed 혹은 undirected이고, source vertex s ∈ V에서 실행된다 하자.

그러면, BFS는 source s에서 reachable한 모든 vertex v ∈ V를 찾고, 종료시 모든 v에 대해 v.d = δ(s, v)이다.

또한, s에서 reachable한 any vertex v != s에 대해, s에서 v까지의 어떤 한 가지 shortest path는 s에서 v.π까지의 shortest path에 edge (v.π, v)를 이은 것이다.

4-5-4. Breadth-First Trees

BFS 프로시져는 그래프를 검색하면서 breadth-first tree를 만든다.

그래프 G = (V, E)와 source s에 대해, G의 predecessor subgraph G_π = (V_π, E_π)를 다음과 같이 정의한다.

V_π = {v ∈ V: v.π ≠ NIL} U {s}

E_π = {(v.π, v): v ∈ V_π - {s}}

Predecessor subgraph G_π는 V_π가 s에서 reachable한 vertices로 이뤄져있고, 

모든 v ∈ V_π에 대해 subgraph G_π가 s에서 v로의 shortest path면서 unique simple path를 포함할 때 G_π는 breadth-first tree라고 한다.

Breadth-first tree는 connected고 |E_π| = |V_π| - 1 이므로 tree다. 우리는 E_π의 edge들을 tree edges라 한다.

(Lemma) BFS 프로시져가 directed 혹은 undirected 그래프 G = (V, E)에 적용되면, 

BFS는 predecessor subgraph G_π = (V_π, E_π)가 breadth-first tree가 되도록 π를 만든다.

아래의 프로시져는 BFS가 이미 breadth-first tree를 compute했다고 가정하고 s에서 v로의 shortest path를 프린트한다.

이 프로시져는 프린트된 path의 vertices 숫자와 linear한 시간으로 실행된다. 각 recursion이 one vertex만큼 짧은 path에 대한 call이기 때문이다.

**기타 Note: 그래프에서 가장 먼저 체크할 것은 1. Connectivity 2. Diameter 3. Degree Distribution 4. Node Centrality