Lecture 9 : Graph Traversal

(1)

Lecture 9 : Graph Traversal ^∗

이 장에서는 그래프를 일정한 순서에 따라서 모두 탐색하는 일 (traversal) 에 관하여 살펴보고자 한다. 그래프의 모든 노드와 에지를 빠짐없이, 또 어떤 제한된 조건하에서 탐색하는 것은 매우 중요한 문제이다. 이 장에서 여러분이 관심가지고 지켜보아야 할 문제는 특정한 Traverability를 가진 그래프의 특성과 더불어 그런 탐색 알고리즘의 복잡도와 그것을 구현하는 능력이다.

9.1 Depth(Breadth)-First Searching

그래프 탐색의 기본은 두 개의 traversal 방법인 DFS와 BFS이다. 한가지 유의해야 할 사실은 이 방법으로 방문할 때 방문되는 순서는 그래프를 표현하는 자료구조에 의해서 결정된다는 것이다. 거의 모든 그래프 알고리즘은 두 탐색방법에 기초하여 구성되어 있다.

문제 9.1.1 Graph algorithm을 위하여 자료구조를 설계하고자 한다. 자료구조를 설계 할 때 생각해야 할 기준은 어떤 것인지 설명하시오.

문제 9.1.2 Adjacency matrix 보다 Adjacency list 가 더 나은 operation 의 예를 들어 보시오.

문제 9.1.3 Directed Acyclic Graph(DAG) 를 위한 자료구조를 설계하시오. 어떤 시점 으로 시작해야할까요?

∗2013년 강의에서 처음 추가된 내용. 이전의 Postman routing 등을 이 장으로 모아서 강의합니다.

흩어진 Hamiltonian관련 자료를 모두 모음

1

(2)

9.2 오일러 경로와 사이클

2

문제 9.1.4 Adjacency matrix와 Adjacency list를 결합하여 둘의 단점을 보완하는 자료 구조를 제시해보시오. Static operation과 Dynamic Operation의 경우를 나누어 설명해 보시오. 예를 들어 특정 edge (u, v) 의 존재여부를 O(1) 만에 확인할 수 있고 모든 edge 를 scanning하는 작업도 O(|E|)에 할 수 있는 자료구조를 제시해보시오.

9.2 오일러 경로와 사이클

위대한 수학자인 오일러 (Euler) 는 1707년 스위스 바젤에서 태어났다. 20대에 한쪽 눈을 실명했으며, 곧 이어 나머지 눈마저 백내장으로 실명하였다. 놀랍게도 오일러 가 발표한 500 여 편의 책과 논문은 맹인이 된 뒤에 발표한 것이다. 오일러는 1783 년 심장병으로 사망한다. 수학계에서 오일러보다 많은 논문을 발표한 사람은 Paul Erdös(pronounced AIR-dish) 뿐이다. 오일러가 그래프를 학문으로 만든 것은 퀘니스 베르그 다리 (Königsberg Bridge) 에서 착안한 것이다.

문제 9.2.1 다음은 어떤 도시의 지도이다. 지도에서 검은색 점은 쓰레기 통을 나타낸다.

가장 빠른 시간에 모든 쓰레기 통을 수거해오는 문제를 그래프 이론적으로 구성해 보시오.

Figure 1: 위 그림에서 검은색 점은 쓰레기통 (trash box) 이다. 쓰레기 청소 차를 이용하여 쓰레기통을 모두 수거하는 가장 합리적인 길을 찾으시오. 그 ” 합리성” 의 기준은 뭐가 되어야 할지 제시하시오.

정의 9.2.1 Define those terms walk, trail, path formally. □

(3)

9.3 그래프 단위 연산 (Graph Operator)

3

정리 9.2.1 A nontrivial connected graph G is Eulerian if and only if every vertex of G has even degree. □

Corollary 9.2.1 A nontrivial connected graph G has an open Eulerian trail if and only if every vertex of G has even degree except two. □

9.3 그래프 단위 연산 (Graph Operator)

그래프를 operand로 하는 다양한 연산 (operation) 이 존재한다. 가장 단순한 연산은 두 그래프를 집합으로 더하는 union이다. 즉 G = G₁∪

G2 일 때 vertex와 edge는 다음과 같의 정의된다.

V = V1

∪V2, E = E1

∪E2

그 다음으로 Zykov가 정의한 G_j = G₁+ G₂에서 join은 다음과 같이 정의된다.

V_j = V₁∪ V₂

이며 edge E_j는 E_j = {(x, y)} x ∈ V1, y ∈ V2 를 추가한다. 그리고 Cartesian Product는 u = (u₁, u₂) , v = (v₁, v₂) in V = V₁× V2. 여기서 u and v 는 adjacent가 된다. 즉 다음과 같은 조건일 때 product edge가 추가된다.

u₁ = v₁ and (u₂, v₂)∈ E(G2) u₂ = v₂ and (u₁, v₁)∈ E(G1)

또 다른 흥미로운 Operation은 Frucht과 Harary가 제안한 corona operation이다.

G₁◦ G2은 G₁의 copy를 G₂의 모든 노드에 대응시키고 해당하는 v∈ G2와 G₁의 모든 정점과 연결하는 것이다. 당연히 G₁◦ G2 ̸= G2◦ G1.

Operation Nodes Edges Union G₁∪

G2 p1+ p2 q1+ q2

Join G₁+ G₂ p₁+ p₂ q₁+ q₂+ p₁· p2

Product G₁× G2 p₁· p2 p₁· q2+ p₂· q1

Corona G₁◦ G2 p1· (1 + p2) q1+ p1· q2+ p2· q1

(4)

4 G

₁

G

₂

G

₁

+ G

₂

G

₁

× G

2 a

b

x

y z

(a; x)

(b; x)

(a; y) (a; z)

(b; y) (b; z)

G

₂

× G

1 (x; a)

(y; a) (z; a)

(x; b) (y; b) (z; b)

G

₁^S

G

₂

a

b

x

y z

Figure 2: 3가지 그래프 연산 (union, join, product)

G

1

◦ G

2

G

2

◦ G

1 Figure 3: Corona Operation for Graph

위에서 정의한 operation을 이용해서 다른 class의 그래프를 정의할 수 있다. 예를 들면 generalized wheel W_i,n은 다음과 같이 정의된다.

Wi,n= Ki+ Cn

단 한가지 유의해야할 것은 2개 이상의 그래프를 연속적으로 조인 (join) 하는 se- quential join작업이다. 이것은 G₁ + G₂+ G₃ + · · · + Gn로 표시되는데 그 결과는 아래와 같이 정의된다.

(5)

5 W

₁

;5

= K

₁

+ C

₇

W

₃

;4

= K

₃

+ C

₄

Figure 4: 일반화된 휠 (generalized wheel)

K

₁

+ C

₄

+ K

₁

K

₁

+ K

₁

+ K

₃

+ K

₁ Figure 5: 순차적 조인 연산 K₁+ C4+ K1, K₁+ K1+ K3+ K1

(G1+ G2)∪

(G2+ G3)∪

· · ·∪

(Gn−1+ Gn)

문제 9.3.1 어떤 그래프의 Cartesian Product를 정의하고, 두 그래프 G 와 H 의 G× H 가 Eurelian이 될 필요충분조건 (necessary and sufficient condition) 을 구하라.

정의 9.3.1 방향 그래프에서 방향있는 오일러 Cycle의 여부를 판정하는 방법을 제시하 시오.

우리는 회전하는 원통의 위치를 감지하고자 한다. 이를 위해서 복잡한 장치를 만들 수 있지만 Eulerian graph와 DeBruijn Sequence를 이용하면 쉽게 해결할 수 있다. 아래는 8개의 방향을 감지하는 장치이다.

(6)

6

0 1 1 1

0 0 1

0 0

1

Figure 6: Wheel의 위치를 감지하기 위한 장치. 1은 전도체 센서이다.

000 010 001

101

100

011 111 110

0 1

1 1

0

Figure 7: 3 bits binary {0,1} Debruijn Sequence construction.

문제 9.3.2 다음 두 mult-igraph(which has undirected edge and directed edge) 가 Eu- lerian cycle을 가지는지를 판단하고 그 근거를 밝히시오.

문제 9.3.3 다음 조건을 만족하는 그래프 중에서 적절한 크기의 예를 제시하시오.

1. G 과 G 모두가 오일러 그래프.

2. G 은 오일러 그래프이지만 G 은 오일러 그래프가 아님.

3. G 도 G 모두 오일러 그래프가 아니지만, 두 개의 그래프 G and G 는 모두 오일러 trail을 가지고 있다.

4. G 는 오일러 trail을 가지고 있으며, 그 중에서 어떤 에지 e 를 제거하면 그 제거된 그래프는 오일러 그래프이다. 즉 G− e is Eulerian

(7)

9.4 Hamiltonian Graph

7

a b c

d

e

f g h

a b c

d

e

f g h

Ga Gb

Figure 8: Find an Euler path or prove that if it does not exist.

9.4 Hamiltonian Graph

Hamiltonian path와 cycle은 William Rowan Hamilton 경의 이름에서 유래한 것이다.

해밀턴 경은 수학자 친구인 Graves와 게임을 토론하던 중 이 문제를 고안하게 되었다.

시작은 정 12면체 (dodecahedron) 그래프에서의 모든 점을 겹치지 않고 지나가는 길을 찾아가는 게임에서 유래되었다. 이 게임은 군론 (Group Theory) 에서 유래한 문제이다.

Hamiltonian Cycle 문제는 대표적인 NP-complete 문제이며, 훨씬 심한 제약조건이라 도, 예를 들어 Planar graph나 3-regular등에서도 그대로 NP-complete 로 남아있다.

아직도 해결되지 못한 여러 Hamiltonian Cycle관련 그래프 문제가 미해결인채로 남아 있다. 그 중에서 밝혀진 가장 대표적인 정리는 아래 뿐이다.

정의 9.4.1 A graph G is hamiltonian if there is a vertex disjoint cycle covering all vertices of G. Or G is called traceable if it contains a Hamiltonian path.

정리 9.4.1 Let S be a set of vertices of G. If G is hamiltonian, then

ω(G− S) ≤ |S|

, where ω(G) 는 연결성분의 수를 나타난다. 등호가 성립하면 G− S 는 hamiltonian path를 가진 hamiltonian traceable이다.

중요한 사실은 G 가 Hamiltonian임을 알 때 위 사실이 성립한다는 것이다. 역으로 아래 부등호가 성립한다고 해도 그것이 Hamiltonian이 아닐 수가 있다. 따라서 어떤 그래프가 Hamiltonian인지의 여부를 판단하는데 위의 정리는 실용적이지 못하다. 왜냐하면 이미 Hamiltonian임을 알고 있어야 함을 가정하기 때문이다. 우리가 가장 관심을 가지는

(8)

8

문제는 query graph G 가 hamiltonian인지의 여부이다. 그러나 위의 정리 (theorem) 은 어떤 그래프가 hamiltonian이 아님을 밝히는 대우명제로는 이용가능하다. 즉 어떤 vertex set S 를 잡아서 그것이 ω(G− S) > |S| 임을 보이면 이 그래프는 Hamiltonian graph가 아님은 확실해진다.

정의 9.4.2 A graph G is called tough, if it holds ω(G− S) ≤ |S|

문제 9.4.1 다음 Herschel graph가 Hamiltonian이 아님을 위의 정리를 이용해서 밝히 시오.

Herschel Graph

1

2

3 4

5 6

7

8

9

10 11

Figure 9: Show this Herschel graph is not hamiltonian. { 1,7,8,9,3 }=S를 생각해보 자.

문제 9.4.2 (Bony and Murty, 2012, p.480). A graph is traceable from a vertex x if it has a Hamiltonian x-path. Hamiltonian-connected if any two vertices are connected by a Hamiltonian path. And 1-hamiltonian if it and all its vertex deleted subgraphs are hamiltonian.

Let G be a graph and let H be graph obtained from G by adding a new vertex and joining it to every vertex of G. Show that

1. H is hamiltonian if and only if G is traceable

2. H is traceable from every vertex if and only if G is traceable

3. H is hamiltonian-connected if and only if G is traceable from every vertex.

4. H is 1-hamiltonian if and only if G is hamiltonian

(9)

9

문제 9.4.3 Show that the following graph G_z is 1-hamiltonian, but not hamiltonian- connected.

G

_z

Figure 10: T. Zamfirescu Graph G_z

정리 9.4.2 Dirac’s Theorem

Let G be a graph of order n ≥ 3. 모든 정점의 차수가 n/2 이상 이면 이 그래프는 Hamiltonian이다.

ρ(u)≥ n/2

Prove) 만일 그래프 G 가 위의 조건을 만족하지만 hamiltonian이 아니라고 가정해보자.

우리는 이 그래프에 위이 조건을 만족하는 한도에서 edge를 계속 추가한다. 이렇게 극단의 상황으로 edge가 추가된 그래프를 maximal non-hamiltonian 그래프라고 한다.

즉 non-hmiltonian을 유지하는 한 계속 추가의 edge를 넣는다. 이제 어떤 edge 하나만 추가해도 hamiltonian cycle을 생성된다. 왜냐하면 하나를 추가해도 non-hamiltonian 이 된다면 이전 상황에서 미리 추가가 되었기 때문이다. 아래 그림에서 보듯이 이제 (u, v)를 추가하면 hamiltonian cycle이 만들어 진다. 그 바로 직접의 hamiltonian path 를 나타내면 다음과 같다.

u = v₀ → v1 → . . . vi→ vi+1→ vn−1. . . v_n= v

그런데 u와 이웃한 최소 n 개의 vertex는 v₁부터 v_n₋₁ 사이에 뿌려져 있다. 동시에 v = vn과 이웃한 최소 n 개의 이웃 vertex 역시 같은 구간에 뿌려져 있다. 이런 경우 반드시 그림과 같이 u 와 연결된 v_i, 그리고 v 와 연결된 v_i+1이 존재함을 증명할 수 있다.

(10)

10

즉 (u, v_i)와 (v_i+1, v_n) 에지가 존재한다면 (u, v) 를 사용하지 않고 만들어지는 또 다른 hamiltonian cycle을 구성할 수 있다. 우리는 모든 vertex의 degree가 n/2 이상이면 반드시 이런 (u, v_i), (v_i, vi+1), (v_i+1, vn) edge가 존재함을 contradiction으로 밝히고자 한다.

v에서 k≥ n/2개의 ”빨간 공”을 path의 중간 vertex v1에서 v_n₋₁까지의 정점이 던 진다고 생각해보자. 연결된 edge이다. 이 경우 v_n에서 hamiltonian cycle을 만들어 주지 않게 연결된 vertex는 각 빨간 공이 놓여진 곳의 바로 왼쪽 칸이다. 이 가능한 칸의 수는 전체 n− 2개 중에서 n/2개의 장소를 제외하면 그 개수는 최대 n/2 − 1개이다. 따라서 오른쪽 끝 v_n와 연결된 vertex는 반드시 (v_i, vi+1과 같은 edge를 만들어 줄 수 밖에 없다.

n = 100이라고 가정해보자. n/2 = 50 이다. 50개의 빨간 공을 중간 빈 통 1번부터 99번까지 넣는다고 하자. 이제 우리는 오른쪽에서 50개의 파란색 공을 99개의 통에 던져 넣는다. 단 이 경우 빨간 공이 들어간 곳, 바로 왼쪽에 넣으면 hamiltonian을 만들어 주므로 이것을 금지해야 한다. 99개의 통 중에 50개를 제외하면 49개의 통이 남는다.

그런데 파란색 공은 모두 50개이므로 이 49개의 안전한 곳에 넣어도 한개는 반드시 금지 된 통이 들어갈 수밖에 없다. 따라서 항상 hamiltonian을 만들어 주는 (u, v_i), (v_i+1, v_n) 이 존재할 수 밖에 없다.

u v_i v_i+1 v

Figure 11: Dirac의 정리의 증명

위의 정리 증명에서 알 수 있다시피 두 vertex의 degree가 각각 n/2 이어도 hamil- tonian이 되지만 조금 더 정밀하게 한다면 두 degree의 합이 n 이상이어도 위의 정리는 성립한다. 이것을 Ore의 정리라고 하는데 실은 위 Dirac 정의의 따름정리라고도 할 수 있다.

Corollary 9.4.1 (Ore 1962)

어떤 그래프의 이웃하지 않는 두 정점의 degree의 합이 n 이상이면 hamiltonian이다. G is hamiltonian if it hold for every non-adjacent vertex u and v,

ρ(v) + ρ(u)≥ n

정리 9.4.3 Posa’s Theorem

만일 그래프 G 가 G 의 vertex의 각 degree d_i가 다음 조건을 만족하면 hamiltonian이다.

(11)

11

d1> 1, d2 > 2, . . . di > i for i < n/2

문제 9.4.4 Give an example of a graph G such that 다음 중 Posa의 조건을 만족하는 degree condition을 찾으시오.

1. (2,3,3,3,3,3,3) 2. (3,3,4,4,4,4,4,5,5) 3. (2,3,3,3,3,4) 4. (3,3,4,5,5,5,5,5) 5. (2,3,4,5,5,5,5,5,5,5)

문제 9.4.5 Give an example of a graph G such that 1. Eulerian but not Hamiltonian.

2. Hamiltonian but not Eulerian.

3. Hamiltonian and has an Eulerian trail but is not Eulerian.

4. neither Eulerian nor Hamiltonian, but has an Eulerian trail.

문제 9.4.6 Tournament는 Complete Directed Graph이다. 즉 모든 vertex pair간 edge 의 방향이 존재하는 그래프이다. tournament에는 반드시 하나의 Hamiltonian Path 가 존재함을 밝히시오. (이것을 다르게 해석하면 일종의 먹이사슬이 존재한다는 것과 동일하다.)

문제 9.4.7 K_n,n의 Hamiltonian cycle의 갯수를 구하시요.

(12)

12

문제 9.4.8 G가 해밀토니언 그래프이면 어떤 vertex set S 에 대하여 G− S 는 적어도

|S|개의 component를 가짐을 보이시요.

문제 9.4.9 t-tough Graph 를 설명하시고, 적당한 크기의 3-tough graph 를 그리시 요.(p.288)

문제 9.4.10 (Bondy-Chvátal의 정리 1976).

A simple n-vertex graph is Hamiltonian if and only if its closure is Hamiltonian.

문제 9.4.11 어떤 routine boolean X(G) 은 주어진 그래프가 Hamiltonian cycle이 있는를 판별하는 함수이다. 이 함수를 이용해서 주어진 그래프에 Hamiltonian path가 있는 지를 검사하는 함수를 작성하시요.

정리 9.4.4 If κ(G)≥ α(G), then G has a Hamiltonian cycle(unless G = K2.

정리 9.4.5 (Dirac 1952)

The circumference of a graph is the length of the longest cycle. 2-connected graph with minimum degree k has circumference at least min{n, 2k}.

(13)

9.5 그래프 탐색 방법론

13

위의 경우를 보이는 2 가지 예를 제시해보시요.

문제 9.4.12 서양 장기판 (Chess Board) 에서 Hamiltonian KNIGHT problem 이란, KNIGHT로 움직여서 처음 자기 자리로 돌아올 수 있는가에 관하여 증명하는 문제이다.

이것을 해결하시요.

문제 9.4.13 두 개의 Hamiltonian Graph의 graph Product는 항상 Hamiltonian임을 밝히시요.

문제 9.4.14 Powering of a Graph

k-th power of a graph G는 어떤 vertex x 에서 거리가 k 이하인 모든 vertex를 연결한 그래프를 말한다.¹

(a) 어떤 tree T 의 T²이 hamiltonian임을 보이시요. (k-Tree) (b) 주어진 connected graph G 의 G²가 hamiltonian임을 보이시요.

k-tree는 유용하게 쓰일 수 있는 그래프이다. 그런데 왜 tree가 아닌데 tree라고 할까

? 노드가 100개이 어떤 트리 T 의 2-Tree의 모양이 어떤 모습일지를 한번 생각해보자.

멀리서 보면 Tree 같지 않을까 ?

9.5 그래프 탐색 방법론

그래프를 탐색하는 방법, 알고리즘에는 매우 많은 변형이 존재한다. 가장 대표적인 Routing 변형문제는 Chinese Postman Problem 이다.

어떤 문헌에 보면 중국 우편배달부문제라 번역하고 있는데 이는 좀 잘못된 번역이다.

이 문제는 중국출신 수학자 Guan Meigu이 고안한 “우편배달부” 문제이다. Routing

1 그래프의 제곱승은 해당 그래프의 adjacency matrix의 Boolean 곱과 같다.

(14)

14

T T²

Figure 12: 어떤 트리의 제곱과 Hamiltonian 특성.

문제는 여러 version이 있으므로 이를 좀 정리할 필요가 있다. 중국배달부 문제는 그래 프에서 모든 정점과 모든 edge를 한번 이상 방문한 뒤 다시 돌아오는 길 중에서 최적의 길, 예를 들면 가장 짧은 길 (cycle) 을 찾는 문제이다.

문제를 이렇게 생각하면 된다. 배달부가 배달해야할 집들은 edge상에 존재한다.

배달부는 아무런 제약조건없이 모든 집에 배달을 해야한다. 즉 edge는 반드시 방문해야 한다. 단 중복도 가능하다. edge중복을 허용한다는 말은 vertex까지 허용한다는 것을 의미한다.

이 문제는 모든 vertex가 even degree이면 Eulerian cycle이 있으므로 문제는 간단하 게 해결된다. 즉 전체 edge의 sum이 정답이 된다. 그런데 아래 예와 같이 몇 개의 홀수 vertex가 존재하면 문제는 복잡해진다. 만일 4개 대각선 edge의 차수를 증가시켜서 degree를 모두 짝수로 만든다면 늘어가는 (중복으로 지나가야 하므로) 4 + 4 + 4 + 4

= 16 이 되지만 모든 vertical edge를 추가하면 1∗ 6 + 2 ∗ 2 = 10 등을 추가하면 10만 증가하므로 최선이 될 수 있다. 따라서 문제는 odd vertex 중에서 가장 짧은 길이의 쌍을 찾아서 그것에 새로운 trail을 추가하는 것으로 이것은 결국 특정한 개수의 그래프에서의 maximum weight matching과 관계가 있다.

(15)

15

7 4 1 1 4

3 2 3

1 2 2

1 3 2 3

4 1 1

4

7 a b

c

d

f e g

h i

j

k

l

Figure 13: 홀수 차수의 degree를 가진 그래프, 또는 네트워크

문제이름 방문 vertex 방문 edge 제한조건

Hamiltonian Cycle 모두, 중복불가 관심없음 Cycle Hamiltonian Path 모두, 중복불가 관심없음 Path

Eulerian Cycle 관심없음 모두, 중복불가 Closed Trail Eulerian Path 관심없음 모두, 중복불가 Trail

Spanning tree 모두 중복불가 Tree

Spanning Trail 모두, 중복가능 중복불가 Closed Trail Traveling Salesman 모두, 중복가능 중복가능 Walk Chinese Postman 관심없음 모두를, 중복가능 walk Shortest (u, v)-path u와 v를 포함 관심없음 최단 path

문제 9.5.1 Chinese Postman Problem 을 Hyper Cube Q_k 에 적용하여 풀어보시요.

Q4에서 이 문제를 풀어보시요. 전체 길이는 얼마인가 ? 단 edge weight는 모두 단위 길이인 1로 계산한다. 그리고 이것은 일반적인 Q_k경우에 대입하여 풀어보시오. □

문제 9.5.2 Another Variation: 게으른 배달부 (Lazy Postman)

좀 게으른 우편 배달부 (Postman) 가 있다. 이 배달부는 집 (H) 에서 출발하여 버스를 타고는 우체국 (P) 에 도착한다. 우체국에서 도착해서는 배달할 우편물을 들고 전 지역

(16)

16

(edge) 에 배달한 후 우체국에 들르지 않고 바로 집으로 간다. 우편물은 각 거리 (edge) 를 따라 늘어선 집에 모두 배달해야 한다. 즉 모든 지역 (edge) 에 우편물을 배달한 뒤에 다시 근무지로 돌아와서 업무보고를 하지 않고 바로 자기 집으로 가버린다. 만일 도로 망이 아래 그림과 같은 경우 이 배달부가 가장 빠르게 처리할 수 있는 시간은 얼마인지 계산해보시오. 단 우편물을 배달할 경우나 그렇지 않을 경우에도 배달 시간은 모두 동일하다. 아래 그래프에서 각 edge의 숫자는 시간 (분 min.) 을 나타낸다. □

Lecture 9 : Graph Traversal