주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프

Presentation on theme: "주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프"— Presentation transcript:

1 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

2 쾨니스버그의 다리들과 그래프 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7

3 한 줄로 그리기 문제: 다음의 그래프 중 한 정점에서 시작해서 연결선을 한 번만 지나면서 그래프를 다 그릴 수 있는 것은 어는 것인가?

4 오일러 경로(Eulerian path) 그래프 G의 오일러 경로는 G의 모든 연결선을 한번만 방문하는 경로이다. 닫힌 오일러 경로(closed Eulerian path)를 오일러 순환(Eulerian cycle 혹은 Circuit)이라고 한다. 오일러 순환이 존재하는 그래프를 오일러 그래프라고 한다.

5 <정리> 오일러 경로를 갖기 위한 필요충분 조건
2개 이상의 정점을 갖는 연결 그래프에서 홀수 차수(odd degree)를 갖는 정점이 하나도 없거나 오직 두 개만 존재해야 한다. 홀수 차수를 갖는 정점을 홀수점(odd vertex)라고 부르면, 그래프가 오일러 경로를 갖는 것과 그래프가 0 혹은 2개의 홀수점을 갖는 것은 동치 관계(equivalence relation)이다. 특히 모든 정점이 짝수 차수를 가지면 이 그래프는 오일러 그래프이다.

6 출발점과 종료점이 다른 경우 출발점과 종료점이 일치하는 경우

7 홀수점이 2개인 그래프는 한 줄로 그리기가 가능하며, 이 때 오일러 경로는 한 홀수점에서 시작하여 또 다른
<정리> 홀수점이 2개인 그래프는 한 줄로 그리기가 가능하며, 이 때 오일러 경로는 한 홀수점에서 시작하여 또 다른 홀수점에서 끝나야 한다. deg=2 deg=3 a b a b (시작점) d c c d deg=3 deg=2 (종료점)

8 예: 오일러 경로를 갖는 그래프 시작점 종료점 deg=3 deg=4 deg=3 deg=2 a d a b c d b c e f

9 예: 오일러 순환을 갖는 그래프 deg=4 deg=4 deg=4 deg=2 a a b c d b c d e f g e f g

10 예제 다음의 그래프는 오일러 경로를 갖고 있는가? deg=3 deg=3 deg=3 deg=6 deg=3 deg=3 deg=3
a b deg=3 deg=6 deg=3 f g c deg=3 deg=3 e d

11 세일즈맨의 고민 마을 A에서 출발해서 모든 마을들을 한번만 방문하고 마을 B에 도착할 수 있을까? A B

12 해밀톤 경로(Hamitonian path)
그래프 G={V,E}에서 모든 정점을 정확히 한 번만 지나는 경로를 해밀톤 경로(Hamilton path)라고 한다. 해밀톤 순환(Hamiltonian cycle 혹은 circuit) 그래프 G={V,E}에서 모든 정점을 정확하게 한 번만 포함하는 순환을 해밀톤 순환이라고 한다.

13 G2는 해밀톤 경로는 존재하지만 해밀톤 순환은 존재하지 않는다. G3는 해밀톤 경로와 순환이 존재하지 않는다.
예: G1은 해밀톤 순환이 존재한다. G2는 해밀톤 경로는 존재하지만 해밀톤 순환은 존재하지 않는다. G3는 해밀톤 경로와 순환이 존재하지 않는다. a b c a a b c b d f c g f e e d e g d G1 G2 G3

14 예제: 방문 판매원 문제(traveling salesman problem)
해밀톤 순환은 1857년에 만들어진 Icosian 퀴즈 문제에서 비롯되었다. 이 퀴즈 문제는 12면체의 20개의 각 정점에 도시 이름을 적고 어느 한 도시에서 출발하여 모서리를 따라서 다른 모든 19개의 도시를 방문하고 처음 출발했던 도시로 돌아오는 게임이다. 물론 각 도시는 단 한번만 방문할 수 있다. 1 20 13 2 19 5 14 12 6 18 15 17 11 16 7 8 10 9 3 4

15 많은 구멍을 뚫어야 하는 금속판이 있다. 시간과 경비를 절약 하기 위해서 드릴은 가능한 빨리 이동해야 한다.
예제: 프레스에 구멍을 뚫는 문제 많은 구멍을 뚫어야 하는 금속판이 있다. 시간과 경비를 절약 하기 위해서 드릴은 가능한 빨리 이동해야 한다. 금속판의 구멍은 정점을, 드릴이 구멍 사이를 움직이는 시간 을 연결선의 숫자로 표시하였다. 어떻게 모든 구멍을 가장 빠른 시간 안에 뚫을 수 있을까? 12 9 7 15 16 4 2 8 3 13 11 6 14 10

16 많은 구멍을 뚫어야 하는 금속판이 있다. 시간과 경비를 절약 하기 위해서 드릴은 가능한 빨리 이동해야 한다.
예제: 프레스에 구멍을 뚫는 문제 많은 구멍을 뚫어야 하는 금속판이 있다. 시간과 경비를 절약 하기 위해서 드릴은 가능한 빨리 이동해야 한다. 금속판의 구멍은 정점을, 드릴이 구멍 사이를 움직이는 시간 을 연결선의 숫자로 표시하였다. 어떻게 모든 구멍을 가장 빠른 시간 안에 뚫을 수 있을까? 12 9 7 15 16 4 2 8 3 13 11 6 14 10

17 해밀톤 경로의 의미 해밀톤 경로를 찾는 문제는 컴퓨터 공학의 여러 문제에서 나타난다.
Traveling sales man Gray codes 하지만 해밀톤 경로를 찾는 문제는 매우 어려운 문제이다: NP-complete! 이에 비해 오일러 경로를 찾는 문제는 O(N) 시간이 걸린다.

18 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

19 방향 그래프(directed graph, digraph) 그래프 G={V,E}에서 연결선의 두 정점이 순서쌍일 때

20 연결선이 시작하는 정점을 시점(initial point), 연결선이 끝나는 정점을 종점(terminal point)라고 한다.
방향 그래프의 정점 v에서 v를 종점으로 하는 연결선의 개수를 진입 차수(indegree)라고 하며, v를 시점으로 하는 연결선의 수를 진출 차수(outdegree)라고 한다. 예: 정점 v3의 진입 차수는 3이며, 정점 v2의 진출 차수는 2이다. v2 e4 v4 e1 e5 e3 v1 v6 e2 e6 v3 v5

21 진입 차수가 0인 정점을 소스(source)라고 하며, 진출 차수가 0인 정점을 싱크(sink)라고 한다.
예: 정점 v1과 v5는 진입 차수가 0으로 모두 소스에 해당되며, 정점 v3와 v6는 진출 차수가 0으로 싱크에 해당된다. v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6

22 강한 연결 방향 그래프(strongly connected diagraph)
방향 그래프 G의 두 정점 u, v에서 u에서 v로의 경로가 존재하고, v에서 u로의 경로가 존재하면 u와 v는 강하게 연결되었다고(strongly connected) 한다. 방향 그래프 G의 모든 정점의 쌍이 강하게 연결되어 있으면 이 그래프를 강한 연결 방향 그래프라고 한다. 약한 연결 방향 그래프(weakly connected diagraph) 방향 그래프 G에서 방향성이 없는 연결선으로 이루어진 그래프를 G'라고 하자. G'의 모든 두 개의 정점에 대해서 경로가 존재하면 약한 연결 방향 그래프라고 한다. 강한 연결 요소(strongly connected component) 강한 연결 그래프의 최대 부분 그래프이다.

23 예: 그래프 G는 모든 두 정점 사이에 경로가 존재하므로 강한 연결 그래프이다. 하지만 그래프 H는 a와 e 사이에 경로가 존재하지 않는다. 하지만 H의 연결선에서 방향성을 제외할 경우 모든 두 정점 사이에는 경로가 존재한다. 따라서 H는 약한 연결 방향 그래프이다. G H G의 강한 연결 요소

24 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

25 가중 그래프(weighted graph)
가중 그래프 G는 G=(V,E,W)로서 정의된다. W는 각 연결선에 주어지는 가중치의 집합을 의미한다. 40 2 40 4 2 4 10 10 40 30 30 10 30 15 15 15 10 20 1 10 20 6 1 10 20 6 30 10 30 10 30 20 10 20 3 5 20 3 5

26 최단 경로 알고리즘 Dijstra 알고리즘 Bellman-Ford 알고리즘

27 [알고리즘] Dijstra 최단 경로 알고리즘
입력: 그래프 G={V,E,W}, V={1,2,3,...,n} 결과: 소스(source) 1에서 다른 정점으로의 최단 경로와 비용 C[i,j] : 연결선 e=(i,j)의 비용(가중치) D[i] : 소스 1에서 정점 i까지 경로의 비용 S={1}  초기 단계 for i=2 to n    D[i] = C[1,i]  /* 1에서 노드 i까지의 비용 */ while (V≠S)    V-S의 정점 중에서 D[w]가 최소값인 정점 w를 선택한다.    w를 S에 합한다.(S = S +{w})    for v ∈ V-S (S를 제외한 모든 정점들에 대해서)        D[v] = min(D[v], D[w]+C[w,v]) for w ∈S

28 예제 초기 단계 S={1}, D[2]=10, D[3]=30, D[4]=, D[5]= , D[6]=  2 40 4 10
15 1 10 20 6 30 10 20 3 5 초기 단계 2 4 10 1 6 30 3 5 S={1}, D[2]=10, D[3]=30, D[4]=, D[5]= , D[6]= 

29 단계2 단계1 단계3 단계4 S={1,2}, D[3]=25, D[4]=50, D[5]= , D[6]= 
40 4 4 10 10 10 1 15 6 1 15 6 20 3 5 3 5 S={1,2}, D[3]=25, D[4]=50, D[5]= , D[6]=  노드2까지의 최단 경로: 12 S={1,2,3}, D[4]=35, D[5]= 45, D[6]=  노드3까지의 최단 경로: 12 3 단계3 단계4 2 4 2 4 10 10 30 10 10 1 15 6 1 15 6 10 20 20 3 5 3 5 S={1,2,3,4}, D[5]= 45, D[6]= 65 노드4까지의 최단 경로: 12 3 4 S={1,2,3,4,5}, D[6]= 55 노드5까지의 최단 경로: 12 3 5

30 단계5 S={1,2,3,4,5,6} 노드4까지의 최단 경로: 12 3 56 2 4 10 10 1 15 6 10 20 3
40 4 10 30 15 1 10 20 6 30 10 20 3 5

31 Bellman-Ford 알고리즘 소스로부터 특정 정점에 이르는 경로를 선택할 때
각 단계 h 마다 최대 h개의 연결선으로 연결된 경로 중에서 최소값을 갖는 경로를 선택 j 2 Dh(2) d2i 3 d3i 1 Dh(3) i Dh(n-1) dn-1i n-1 Dh(n) dni n Dh[j]: h 단계까지 계산 결과 소스 1에서 각 정점에 이르는 경로의 최소값 Dh[j]+dji : i와 이웃하는 정점들(j)을 통한 i까지의 경로의 비용 dji: 연결선 (j,i)의 비용 이렇게 구한 값 중에서 가장 작은 값이 소스1에서 i에 이르는 h+1개의 연결선으로 구성된 최단 경로가 된다.

32 [알고리즘] Bellman-Ford 최단 경로 알고리즘
입력: 그래프 G={V,E,W}, V={1,2,3,...,n} 결과: 소스(source) 1에서 다른 정점으로의 최단 경로와 비용 djj : 정점 i에서 j까지 연결선의 비용      dii = 0      dij = ∞ if i and j are not directly connected  h :  연결선의 수  Dh[j]: 소스 1에서 정점 j까지 h개까지의 연결선으로 이루어진 경로 중에서 가장 적은 비용의 값 단계1: 초기화     h=0     D0[i] = ∞ for all i ∈ {2,3,...,n}  단계2:     Dh+1[i] = min(Dh[j]+dji) for i,j ∈ {2,3,...,n}     h=h+1  단계2의 절차를 Dh[i]의 변화가 더 이상 발생하지 않을 때까지 반복한다.

33 예제 h=1 D1[2]=10 , D1[3]= 30, D1[4]=, D1[5]= , D1[6]=  (12) (13) 2
40 4 10 30 15 1 10 20 6 30 10 20 3 5 h=1 2 4 10 1 6 30 3 5 D1[2]=10 , D1[3]= 30, D1[4]=, D1[5]= , D1[6]=  (12) (13)

34 h=2 h=3 D1[2]=10, D1[3]=25, D1[4]=40, D1[5]= 50, D1[6]= 
15 6 30 20 3 5 D1[2]=10, D1[3]=25, D1[4]=40, D1[5]= 50, D1[6]=  (12), (12 3) (13 4) (13 5) h=3 2 4 10 10 1 15 6 30 10 20 3 5 D1[2]=10, D1[3]=25, D1[4]=35, D1[5]= 45, D1[6]= 60 (12), (12 3) (12 3 4) (12 3 5) (13 5 6)

35 h=4 D1[2]=10, D1[3]=25, D1[4]=35, D1[5]= 45, D1[6]= 55
15 6 30 20 3 5 D1[2]=10, D1[3]=25, D1[4]=35, D1[5]= 45, D1[6]= 55 (12), (12 3) (12 3 4) (12 3 5) (12  3  5 6) 2 40 4 10 30 15 1 10 20 6 30 10 20 3 5

36 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

37 그래프 순회(graph traversal)
그래프의 모든 정점들을 한번씩 찾아서 방문하는 것을 그래프 순회(graph traversal)라고 한다. 그래프 순회 방법  깊이 우선 탐색(depth first search)  넓이 우선 탐색(breadth first search)

38 깊이 우선 탐색 탐색을 시작하는 정점에서 인접하는 정점 중에서 아직 방문하지 않은 정점을 계속 찾아서 먼저 방문하는 것이다.
이렇게 계속 인접하는 정점을 찾아 방문하다가 더 이상 방문하지 않은 정점이 없으면 가장 최근에 방문했던 정점으로 다시 돌아와서 이 정점에 인접된 정점 중에서 방문하지 않은 정점이 있으면 계속 찾아 나간다. 그리고 더 이상 방문하지 않은 정점이 없으면 다시 가장 최근에 방문했던 정점으로 돌아와서 여기서부터 다시 인접된 정점들을 방문해 나간다.

39 예: 그래프 G의 깊이 우선 탐색에 의한 방문 순서
a 2 9 b c d e b f 10 3 f d g f c i c a g 4 c j g j 5 6 a d d g h 7 e a i f j h 8 f g h G j 방문 순서: a b f c d g j h e i

40 넓이 우선 탐색 시작 정점의 인접 정점들을 모두 방문한 뒤에 이 정점들에 인접한 정점들을 방문하는 것이다.
즉 한 정점에 인접한 정점들은 모두 먼저 방문하고 다음 단계의 인접된 정점들을 찾아간다.

41 예: 그래프 G의 넓이 우선 탐색에 의한 방문 순서
1 a b f 2 3 4 5 c b d e c 7 a g 6 f i 8 j d g f c c 9 g j 10 d h f j h e j i G 방문 순서: a b c d e f g i j h

42 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

43 평면 그래프(planar graph) 그래프 G=(V,E)의 연결선들이 서로 교차하지 않고 평면상에 그릴 수 있는 그래프G를 평면 그래프라고 한다.

44 다음의 그래프들은 동형 그래프(isomorphic graph)이다.
L25

45 예: 비평면 그래프 (a) K5 (b) K3,3

46 평면 그래프의 의미 지도의 그래프 표현은 평면 그래프여야 한다. 전자 회로는 평면 그래프여야 한다.

47 연결선에 따라 구분된 영역을 면(face)이라고 한다.
4 3 1 2 (a) 그래프 G 1 2 3 4 1 1 2 2 (b) 그래프 G에 분할되는 면(faces)

48 <정리> 오일러 정리 연결된 평면 그래프의 정점의 수를 v, 연결선의 수를 e, 면의 수를 f라고 하면 다음과 같은 관계식이 성립한다. v-e+f = 2 <정리> 루프(loop)가 없고 두 개 이상의 연결선이 존재하는(즉, v≥3) 연결된 평면 그래프에서는 다음과 같은 식이 성립한다.           e  ≤ 3v - 6

49 그래프 K5는 v=5, e=10이다. 따라서 3x5-6=9이므로 오일러 정리를 만족하지 않으므로 비평면 그래프이다.
예제: 그래프 K5는 v=5, e=10이다. 따라서 3x5-6=9이므로 오일러 정리를 만족하지 않으므로 비평면 그래프이다. K5 K3,3 K3,3 그래프는 v=6, e=9이다. 이 그래프가 평면 그래프라면 [정리5]의 오일러 정리에 의해서 f=5이다. 그런데 이 그래프는 어떤 면도 세 개의 연결선으로 만들어지지 않는다. 따라서 모든 면은 최소한 4개 이상의 연결선으로 만들어지며 5개 면의 총 차수(degree)는 4x5=20 이상이 되어야 한다. 차수가 20 이상이라면 총 연결선은 10개 이상(e≥10)이 되어야 하므로 현재 그래프는 e=9이므로 이 그래프는 평면 그래프가 될 수 없다.

50 준동형 그래프(homeomophic graph) 임의의 그래프 G에 대해서 한 연결선에 여러 개의 정점을
추가해서 그 연결선을 분할할 수 있다. 이것을 기본적인 세분할(elementary subdivision)이라고 한다. 이와같이 그래프G로부터 기본적인 세분할을 통해서 얻어진 그래프 G'과 G''을 준동형 그래프라고 한다. G’’ G G’

51 Kurantowski 정리와 Kurantowski 그래프
그래프가 그래프K5와 K3,3와 준동형인 부분 그래프를 포함한다면 비평면 그래프이며, 이 역도 성립한다. 그리고 K5와 K3,3;를 Kurantowski 그래프라고 한다. 예제: G'은 G의 부분 그래프이다. 그리고 G‘은 K5와 준동형 그래프이다. 따라서 Kurantowski 정리에 의해서 그래프 G는 K5와 준동형인 부분 그래프를 갖고 있으므로 비평면 그래프이다. G G’ K5

52 주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

53 그래프의 채색(graph coloring)과 색상수(chromatic number)
그래프의 채색은 인접하고 있는 정점들은 서로 다른 색을 갖도록 하면서 그래프의 모든 정점에 색을 할당하는 것이다. 이렇게 칠하기 위해서 필요한 최소한의 색의 수를 그래프의 색상수(chromatic number)라고 하고 χ(G)로 표시한다.

54 예제: 다음 그림의 색상수는 얼마인가? χ(G)=4 G A E I C B F D G J H Y E R F R Y A B I C

55 예제: 완전 그래프 Kn의 색상수는 얼마일까? Kn의 색상수는 n이다. 예제: 이분 그래프 Km,n의 색상수는 얼마일까?
이 값은 m, n에 상관없이 χ(Km,n)=2이다.

56 <정리> 다음 세 가지 명제는 서로 동치(equivalent)이다. (1) G는 이분 그래프이다. (2) χ(G) = 2이다. (3) G의 모든 순환(cycle)의 길이는 짝수이다. <정리>4색 정리(the four color theorem) 평면 그래프의 색상수는 4보다 크지 않다. 즉 χ(G) ≤ 4이다.

57 예제: 그래프 채색의 응용- 스케쥴링(scheduling)
대학교에서 기말 시험을 볼 때 동일한 학생이 수강하고 있는 강좌는 같은 시간에 시험을 보아서는 안 된다. 예를 들어 1번에서 8번까지의 8개의 강좌가 있고 동일한 학생이 수강하는 과목이 1과 2, 1과 5, 1과 8, 2와 7, 2와 3, 3과 4, 4와 7, 4와 6, 5와 6, 6과 7, 7과 8이라고 하자. 이 문제는 수강 과목을 정점으로 하고 동일한 학생이 수강하는 과목들을 연결선으로 하는 그래프로 표시할 수 있다. 그리고 동일한 학생이 수강하는 과목들은 같은 시간에 시험을 볼 수 없으므로 인접하는 정점들은 다른 색을 같아야 하는 그래프 채색의 문제가 된다. 1 2 3 8 4 7 6 5