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

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

1

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

3 왜 그래프인가? 컴퓨터를 하는 사람에게 그래프는 어떤 의미가 있는가?
우리가 풀고자 하는 문제의 본질을 추출하여 단순화된 그림(abstract, 抽象)으로 문제를 표현할 수 있도록 한다. 그래서 우리는 이 단순화된 그림을 통해서 문제를 해결하는 알고리즘을 찾고자 한다.

4 예: Konigsberg의 7개 다리 프러시아의 도시인 Konigsberg(지금은 러시아의 Kaliningrad)는 Pregel강의 양쪽에 위치하고 있었다. 강 가운데는 두 개의 섬이 있고, 도시는 일곱개의 다리로 연결되어 있었다. 문제: 다리를 한번만 건너면서, 모든 다리를 지나서 출발했던 지점으로 다시 돌아 오는 길을 찾는다.

5 앞의 문제를 다시 표현하면, 이 문제를 풀기 위해서 우리가 관심있는 것은? - 육지에서의 길은 의미가 없다.
- 오직 의미가 있는 것은 지나는 다리의 순서이다. 따라서 이 문제는 다음과 같은 추상적 모형(그림)으로 표현할 수 있다. - 육지는 점(vertex, node)으로 표현하다. - 다리는 선(edge)으로 표현한다.

6 위의 세 그림은 이 문제를 표현한 추상화한 그림이라는
점에서는 모두 같다. 왜? 모두 이 문제의 같은 본질(?)을 갖고 있기 때문이다.

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

8 기본 용어 그래프(graph) 그래프 G는 다음의 두 가지 집합으로 구성되며 G={V, E}
로 표시한다. 여기서 V는 정점(vertex)들의 집합이며, E는 정점들을 연결하는 선(edge)들의 집합이다. e1 e2 v3 e3 e5 e6 e9 e10 v2 v1 v4 v6 v8 v5 v7 v9 e4 e7 e8

9 임의의 연결선 e=(u,v)에 대해서 정점 u와 v는 서로
인접(adjacent)했다고 하며, u와 v는 e의 끝점(end point) 이라고 한다. e는 정점 u와 정점 v에 접합(incident)한다고 한다. 연결선의 두 끝점이 같은 정점이면 이 연결선을 루프(loop)라고 한다. 또한 두 개 이상의 연결선이 같은 끝점을 가지면 이 연결선을 다중 연결선(multiple edge)이라고 한다. 이와 같이 다중 연결선이나 루프를 갖는 그래프를 다중 그래프(multiple graph)라고 한다. 그리고 다중 그래프가 아닌 그래프를 구분하여 단순 그래프(simple graph)라고 부르기도 한다.

10 예 e1과 e3, e2와 e4는 다중 연결선이다. e5는 루프이다. v1 e8 e5 e1 e3 v2 e6 v4 e2 e4 e7

11 정점 u에 접합된 연결선의 수를 정점 u의 차수(degree)라고 한다. 차수는 deg(u)와 같이 표기하기도 한다.
v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8 deg(v4)=5 deg(v3)=3,

12 그래프에서 모든 정점의 차수의 합은 모든 연결선 수의 2배이다.
<정리> 그래프에서 모든 정점의 차수의 합은 모든 연결선 수의 2배이다.                          deg(v1)=3, deg(v2)=5, deg(v3)=3, deg(v4)=5이고 연결선 의 수는 8이다. v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8

13 “여러 이성 파트너를 갖고 있는 경우가 남성이 여성 보다 74% 더 많다. 따라서 남성의 이성 관계가 더 난잡하다”
(1994년 시카고 대학 연구 결과) 과연 이 명제는 성립될 수 있는가? 여성(F) 남성(M) 앞의 정리에 의해서 Avg. deg(M) = Avg. deg(M) |M|≈|F|이라면,

14 경로(path) 그래프 G의 모든 정점은 경로가 1이다. 연결선이 존재하는 연속된 정점들(v1, v2, …, vk)을 경로라고 한다. (0<i<k) 경로상의 모든 정점들이 다른 경로를 단순 경로(simple path) 라고 한다. 두 정점 u와 v 사이에 경로가 존재하면 두 정점은 연결(connected)되었다고 한다. 그래프에서 k-1개의 연결선을 제거해도 두 정점 u와 v 사이에 경로가 존재하면 두 정점은 K-연결(k-connected)되었다고 한다.

15 그래프 G의 모든 정점들이 상호 연결되어 있으면 G는 연결 그래프(connected graph)라고 하며,
그렇지 않은 그래프는 비연결 그래프(disconnected graph) 라고 한다. 예: 연결 그래프와 비연결 그래프 v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6

16 길이(length) 두 정점의 경로를 구성하는 연결선의 수를 경로의 길이라고 한다. 닫힌 경로(closed path) 만약 경로 {v1, v2, ... ,vn}에서 v1=vn인 경로  순환(cylcle 혹은 circuit) 3개 이상의 연결선을 갖는 경로에서 어떤 연결선도 중복되지 않은 닫힌 경로(closed path) 순환 그래프(cylcled graph)와 비순환 그래프(acycled graph) 이러한 경로를 갖는 그래프를 순환 그래프(cycled graph), 그렇지 않은 그래프를 비순환 그래프(acycled graph)라고

17 두 정점의 거리(distance)는 두 정점 간의 최단 경로의 길이를 말하며, 직경(diameter)은 그래프 상의 임의의
두 정점 사이의 길이 중 최장 길이, 즉 가장 긴 길이를 말한다. 예 v1과 v6을 연결하는 경로는 {e1, e4, e7}(길이는 3), {e1, e3, e5, e8}(길이는 4), {e1, e3, e5, e6, e7}(길이는 5) 등 여러 가지 경로가 존재하는데 이 중 최단 경로는 {e1, e4, e7}으로 두 정점의 거리는 3이 된다. v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6

18 부분 그래프(subgraph)와 伸張 그래프(spanning graph)
그래프 G={V,E}가 있을 때, V'⊆V이고 E'⊆E인 그래프 G'={V', E'}를 G의 부분 그래프라고 한다. V'=V이고 G‘가 연결 그래프이면 G’는 신장 그래프라고 한다. (a) (b) v2 e4 v4 v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6 e1 v1 e3 v6 e2 e5 v3 v5 (c) v2 e4 v4 e1 그래프 b와 c는 a의 부분 그래프 이고 c는 a의 신장 그래프이다. v1 e3 v6 e2 e5 v3 v5

19 동형 그래프(isomorphic graph) 임의의 두 그래프 G={V, E}와 G'={V', E'}에 대하여
다음의 조건을 만족하는 함수가 1:1 관계의 함수이면 두 그래프 G와 G'를 동형 그래프라고 한다.       함수 f: v → v' (v∈V, v'∈V')       (x,y) ∈ E ⇔ (f(x), f(y)) ∈ E' 그리고 이 관계가 성립하는 함수 f를 동형(isomophic)이라고 한다. a c b d e g f h

20 예: 동형 그래프들 v1 v2 v3 v4 v1’ v2’ v3’ v4’ v1 v2 v3 v4 v5 v1’ v2’ v3’ v4’

21 완전 그래프(complete graph) 그래프G={V, E}가 모든 정점 사이에 연결선이 존재하면
완전 그래프는 Km으로 표시한다.(m은 정점의 총 수) (b) K4 (c) K5 (a) K3

22 이분 그래프(bipartite graph)
그래프G={V, E}의 V가 X⋂Y=∅인 두 부분 집합 X와 Y로 갈라지고, 연결선이 x∈X, y∈Y인 (x,y)의 쌍으로 이루어지면 G는 이분 그래프라고 한다. 또한 X의 모든 정점과 Y의 모든 정점 사이에 연결선이 존재하면 G를 완전 이분 그래프(complete bipartite graph) 라고 하며 Km,n으로 표시한다. (m은 X의 개수, n은 Y의 개수)

23 이분 그래프 완전 이분 그래프 X Y a b c d e f

24 정규 그래프(regular graph) 그래프 G={V, E}의 모든 정점의 차수가 같으면, G를 정규 그래프라고 한다. 예: deg=4인 정규 그래프

25 예: 정규 그래프들

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

27 그래프의 표현 인접 행렬(adjacent matrix) 인접 리스트(adjacent list)
접합 행렬(incidence matrix)

28 인접 행렬 인접 행렬은 그래프를 구성하는 두 정점들 간에 연결선의 존재 여부를 나타내는 방법이다. 그래프를 구성하는
정점들의 집합을 V={1,2,3,...,n}이라고 하면 그래프는 n x n의 행렬로서 표현되는데 행렬의 각 요소는 다음과 같이 정의된다. aij = 1: 두 정점 i와 j 사이에 연결선이 존재하는 경우          0: 두 정점 i와 j 사이에 연결선이 없는 경우

29 예: 인접 행렬로 표현한 그래프의 예 M = 2 1 3 4 5 e1 e2 e3 e4 e5 1 2 3 4 5 0 1 1 0 0
M =

30 인접 리스트 인접 리스트는 그래프의 각 정점과 연결선을 갖는 정점들을 연결 리스트(linked list)로 표현하는 방법이다.
2 1 3 4 5 e1 e2 e3 e4 e5

31 접합 리스트 그래프를 표현하는 또 다른 방법은 각 정점에서 접합되는 연결선의 존재 여부를 행렬로서 나타내는 방법이다.
V={1,2,3,...,m}, E={e1,e2,..., en}인 그래프는 m x n의 행렬로서 표현되는데 행렬의 각 요소는 다음과 같이 정의된다. aij =  1: 연결선 ej가 정점 i에 접합된 경우           0: 그렇지 않은 경우

32 예: 접합 리스트로 표현한 그래프 M = 2 e4 4 e1 e3 1 e5 e2 3 5 e1 e2 e3 e4 e5
M =