이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다

Chapter 08. 그 래 프

학습목표 그래프의 개념과 관련 용어 이해 그래프 이론 관련 정리의 이해 다양한 그래프의 종류와 형태 살피기 그래프 표현 방법 익히기 그래프 탐색 방법과 과정의 이해

정원사의 고민 어느 호수 공원은 그림과 같이 시냇물을 막아 인공호수와 3개의 섬을 만들고 이 섬들을 다리와 징검다리로 이어서 조성되어 있다. 이 정원은 아주 인기가 있어 특히 휴일에는 많은 사람들이 찾는다. 그러나 사람들은 다리를 아무렇게나 건너면서 관람을 하기 때문에 좁은 다리가 아주 혼잡해져서 사람들은 이 다리를 건너기 위하여 긴 줄을 서느라 아주 피곤해 한다. 수석 정원사는 이러한 혼잡을 피하고자 정원의 남쪽에서 시작하여 다리와 징검다리를 한 번씩만 그리고 모두 건너서 건너편 원예원에 이르는 관람로를 만들기로 결정을 하였다. 그러나 아무리 생각하여도 해결책이 떠오르지 않을 때, 그 정원사의 젊은 조수 오일러는 다리 하나를 더 만든다면 그러한 관람로를 만들 수 있다고 말했다. 과연 정원사는 어이에 다리를 놓아야 할까?

Section 01. 기본 개념 그래프 이론의 출발 오일러(Leonard Euler)의 쾨니히스베르크 다리문제

기본 개념(계속) 쾨니히스베르크 다리 문제에서의 그래프 이론

기본 개념(계속) [정의1] 그래프(graph) 집합 : 공집합이 아닌 정점(vertex)들의 집합 집합 E : 에지(edge)들의 집합 에지 : 서로 다른 정점 의 쌍

기본 개념(계속) 방향 그래프와 무방향 그래프 [그림 8.3]

기본 개념(계속) [예제01] [그림 8.3]의 그래프 (1), (2)를 집합으로 나타내어라. [풀이] (1) 주어진 그래프를 G 라고 하자. 그래프 G 는 무방향 그래프다. (2) 주어진 그래프를 H 라고 하자. 그래프 H 는 방향 그래프므로 에지 순서에 유의해야 한다.

기본 개념(계속) 다중그래프(multi-graph) 단순그래프(simple-graph) [정의2] 두 정점 사이에 두 개 이상의 에지가 있는 그래프 단순그래프(simple-graph) 다중그래프가 아닌 그래프 [정의2] 루프(loop) 에지 e의 끝점이 서로 같은 정점일 때

기본 개념(계속) [예제02] 다음 그래프 G를 그림으로 나타내어라. (1) G=(V, E) V={a, b, c} E={(a, b), (b, c), (a, a)} (2) G=(V, E) V={a, b, c, d} E={(a, b), (b, c), (a, a), (d, d), (b, d)} [풀이]

기본 개념(계속) (1) (2)

기본 개념(계속) [정의3] 차수(degree) 그래프 G 의 임의의 정점 v 를 끝점으로 하는 에지의 수 deg(v) 표시

기본 개념(계속) [예제07] 다음 그림을 그래프 G 로 나타내고 각 정점의 차수를 구하여 라. [풀이]

기본 개념(계속) G=(V, E) V={a, b, c, d} E={(a, b), (a, c), (a, c), (b, c), (c, d)} 로 나타낸다. 또한 차수는 정점에 연결된 에지의 수이므로 주어진 그래프의 각 정점의 차수는 다음과 같다. deg(a)=3, deg(b)=2, deg(c)=4, deg(d)=1

기본 개념(계속) [정리01] 그래프 G 의 정점의 수가 n 개, 에지의 수가 e 개면 다음이 성립한다. [증명] 그래프에서 에지는 항상 두 개의 정점을 연결한다. 따라서 정점 vi 와 vj 를 연결한 에지를 ei 라고 했을 때 ei 는 vi 에 대 한 차수를 계산할 때와 vj 에 대한 차수를 계산할 때 중복하 여 계산된다. 이처럼 하나의 정점에 대해 에지가 항상 중복 계산되므로 위 정리가 성립한다.

기본 개념(계속) [정리02] 그래프 G=(V, E)에서 홀수의 차수를 갖는 정점의 수는 반드 시 짝수 개 존재한다. [증명] V1, 홀수의 차수를 갖는 정점의 집합을 V2라고 하면 [정리 01]에 의해 홀수가 짝수 개 even

기본 개념(계속) [예제11] 5 개의 정점이 각각 1, 2, 3, 4, 5의 차수를 갖는 그래프가 존재하는지 확인하여라. [풀이] 주어진 5 개의 정점에는 홀수 개의 차수를 갖는 정점이 3개 존재한다. 그런데 [정리02]에 의하면 그래프에서 홀수 개 의 차수를 갖는 정점은 반드시 짝수 개 존재하므로 정리에 위배된다. 또한 차수들의 합이 홀수므로 [정리01]에도 위 배된다. 따라서 주어진 차수를 갖는 그래프는 존재하지 않는다.

기본 개념(계속) [정의4] [정의5] 경로(path) 정점과 에지의 연속으로 구성된 와 같 은 형태 길이(length) 정점과 에지의 연속으로 구성된 와 같 은 형태 [정의5] 길이(length) 경로를 구성하는 에지의 개수 닫혀있다(closed) 어떤 경로의 처음과 끝의 정점이 같은 경우인 경우에 이 경로를 닫혀있다고 한다. 순환(cycle) 닫혀있는 경로

기본 개념(계속) [예제13] 주어진 그래프에서 a 에서 d 로의 임의의 경로를 구하고 해당 경로의 길이를 구하여라. [풀이] (a, e, d)는 길이 2인 경로다. (a, b, e, c, d)는 길이 4인 경로다. 이외에도 많은 경로들이 존재한다.

기본 개념(계속) [예제14] 주어진 그래프에서 정점 a 를 포함하는 임의의 순환을 구하고 해당 순환의 길이를 구하시오. 길이가 3인 순환 : 길이가 4인 순환 : 길이가 5인 순환 :

기본 개념(계속) [정의6] 부분그래프(subgraph) 그래프 G=(V, E)라 할 때 V’⊆V이고 E’⊆E인 V’와 E’로 구성된 그래프 G’=(V’ ,E’) 신장부분그래프(spanning subgraph) 그래프 G=(V, E)라 할 때 V’=V고 E’⊂E인 그래프 G’=(V’ ,E’ )

기본 개념(계속) [정의7] [정의8] 연결그래프(connected graph) 모든 정점들 사이에 경로가 존재하는 그래프 거리(distance) 그래프 상의 임의의 두 정점 a와 b 사이의 최단 경로 d(a, b) 로 표시 직경(diameter) 그래프 상의 임의의 두 정점간의 거리 중 최장 거리

기본 개념(계속) [예제19] 그래프 G 가 아래와 같이 주어졌을 때 물음에 답하여라. (1) 정점 a 와 d 간의 거리를 구하여라. (2) 정점 c 와 e 간의 거리를 구하여라. (3) 그래프 G 의 직경을 구하여라.

기본 개념(계속) [풀이] (1) 정점 a 와 d 간의 최단 경로는 (a, d)므로 d (a, d)=1 이다. (2) 정점 c 와 e 간의 최단 경로는 (c, d, e) 또는 (c, b, e)므로 d (c, e)=2 다. (3) 그래프 G 의 직경은 d (a, f )=3 이다.

Section02. 오일러와 해밀턴 순환 [정의9] 오일러 경로(Euler path) 그래프 G=(V, E)에 대해 G 안의 모든 정점과 모든 에 지가 포함되는 경로 오일러 순환(Euler cycle) 그래프 G=(V, E)에 대해 G 안의 모든 정점과 모든 에 지가 포함되는 순환 오일러 그래프(Euler graph) 오일러 순환이 포함된 그래프

오일러와 해밀턴 순환(계속) [예제22] 다음 그래프에서 오일러 순환을 찾아라. [풀이] 오일러 순환에는 (a, b, e, c, d, e, a)가 있으며, 이외에도 여러 개의 오일러 순환이 존재한다.

오일러와 해밀턴 순환(계속) [정리03] [정리04] 그래프 G=(V, E)가 오일러 순환을 갖기 위한 필요충분조건 갖는 것이다.

오일러와 해밀턴 순환(계속) [정의10] 해밀턴 경로(Hamiltonian path) 그래프 G=(V, E)에 대해 G 안의 임의의 정점에서 출발 하여 그래프의 각 정점이 한 번씩 만 나타나도록 만들 어진 경로 해밀턴 순환(Hamiltonian cycle) 정점을 한 번씩만 지나고 다시 출발 정점으로 돌아오는 순환 해밀턴 그래프(Hamiltonian graph) 해밀턴 순환이 포함된 그래프

오일러와 해밀턴 순환(계속) 해밀턴 퍼즐의 그래프 12 면체의 입체도형에 도시 이름을 주고 어떤 도시에서 출발하여 주어진 길을 따라 각 도시를 한 번만 방문하고 다시 출발 도시로 돌아오는 퍼즐

Section03. 여러 가지 그래프 [정의11] 평면그래프(planer graph)

여러 가지 그래프(계속) [정리05] 그래프 G 를 연결된 평면그래프라고 하고, 정점의 수를 v, 에지의 수를 e, G 에 의해 평면상에 형성되는 영역의 수를 r이라고 하면 다음 공식이 성립한다. r = e – v + 2 이를 오일러의 공식(Euler’s formula)이라고 한다.

여러 가지 그래프(계속) [예제28] 다음 그래프가 평면그래프인지 판별하고, 오일러의 공식이 성 립함을 보여라. [풀이] 주어진 그래프는 정점을 제외하고는 에지가 교차하는 부분이 없도록 다음과 같이 수정할 수 있다.

여러 가지 그래프(계속) 그러므로 주어진 그래프는 평면그래프다. 그래프의 정점의 수 v = 6, 에지의 수 e = 9, 영역의 수 r = 5 므로 오일러 공식 v – e + r = 6 – 9 + 5 = 2 가 되어 성립한다.

여러 가지 그래프(계속) [정의12] 완전그래프(complete graph) 그래프 G 의 모든 정점들간에 서로 에지가 존재 n 개의 정점을 가진 완전그래프를 Kn으로 표시

여러 가지 그래프(계속) [정의13] 정규그래프(regular graph) 그래프 G 의 모든 정점들이 같은 차수를 갖는 경우 k-정규그래프 차수가 k인 정규그래프 2-정규그래프 4-정규그래프

여러 가지 그래프(계속) [정의14] 이분그래프(bipartite graph) 그래프 G 에서 정점의 집합 V 가 V = V1∪V2 면서 V1∩V2 =Ø을 만족하는 두 집합 V1 과V2 로 분리되고, 그 래프의 모든 에지가 V1 의 한 정점에서 V2 의 한 정점으 로 연결되는 그래프

여러 가지 그래프(계속) [정의15] 완전 이분그래프(complete bipartite graph) 그래프 G 의 정점들의 집합 V 를 다음의 성질을 만족하 는 두 부분집합으로 나누자. V = V1∪V2 V1∩V2 =Ø |V1|=m, |V2 |=n

여러 가지 그래프(계속) 이때 V1 의 한 정점과 V2 의 한 정점 사이에는 에지가 존재하지만 V1 의 정점들 사이와 V2 의 정점들 사이에는 에지가 존재하지 않는 경우의 그래프 K2,3 완전이진그래프 K3,3 완전이진그래프

여러 가지 그래프(계속) [정의16] 동형그래프(isomorphic graph) 두 그래프 G1=(V1, E1 ) 과 G2=(V2, E2 )가 있을 때 V1에 서 V2 로의 전단사함수 f 가 존재하여 임의의 정점 a, b∈V1 에 대해 (a, b)∈E1 일 필요충분조건 (f(a), f(b))∈E2 를 만족하는 경우

Section04. 그래프의 표현 - 인접행렬 인접행렬을 이용한 그래프 표현 방법 그래프 G 가 n 개의 정점을 갖는다고 하면 G 의 인접행렬은 nⅹn행렬이다. 이 인접행렬을 A=[aij]라고 할 때 각 원소의 값은 다음과 같이 나타낼 수 있다.

그래프의 표현 – 인접행렬(계속) [예제31] 다음 그래프를 인접행렬로 나타내어라. [풀이]

그래프의 표현 – 인접리스트 인접리스트 인접행렬의 n 행들의 값을 n 개의 연결리스트로 표시 인접리스트 방식은 각 정점에 인접한 정점들을 일일이 열거하는 것 순서와 무관 필드 구성 시작정점 : 헤드(head) 첫 번째 필드 : 정점 두 번째 필드 : 링크(link)

[예제31]의 그래프를 인접리스트로 나타내어라. 그래프의 표현 – 인접리스트(계속) [예제33] [예제31]의 그래프를 인접리스트로 나타내어라. [풀이]

Section05. 그래프 탐색 - 깊이우선탐색 [예제36] 다음 그래프 G=(V, E) 에서 f 를 기준으로 깊이우선탐색한 결과를 그림으로 나타내어라.

그래프 탐색 – 너비우선탐색 [예제38] 다음 그래프 G=(V, E) 에서 a 를 기준으로 너비우선탐색한 결과를 그림으로 나타내어라.

Thank you ehanbit.net