그래프그래프

8 8 ^{장 장 그래프 그래프}

• 기본 개념

• 오일러와 해밀턴 순환

• 여러 가지 그래프

• 그래프의 표현

• 그래프 탐색

• 기본 개념

• 오일러와 해밀턴 순환

• 여러 가지 그래프

• 그래프의 표현

• 그래프 탐색

학습목표 학습목표

22

그래프의 개념을 이해하고 용어를 익힌다 . 그래프 이론과 관련된 정리들을 이해한다 . 다양한 그래프의 종류와 형태를 살펴본다 . 그래프를 표현하는 방법을 익힌다 .

그래프를 탐색하는 방법과 과정을 이해한다 .

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

33

기본 개념 기본 개념

[ 그림 8-1] 쾨니히스베르크 다리

그래프 이론의 출발

오일러 (Leonard Euler) 의 쾨니히스베르크 다리문제

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

44

기본 개념 기본 개념

[ 그림 8-2] 쾨니히스베르크 다리의 그래프 모델

쾨니히스베르크 다리 문제에서의 그래프 이론

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

55

기본 개념 기본 개념

[ 그림8-3] 무방향그래프와 방향그래프

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

66

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

77

기본 개념 기본 개념

다중그래프 (multi-graph)

두 정점 사이에 두 개 이상의 에지가 있는 그래프

단순그래프 (simple-graph)

다중그래프가 아닌 그래프

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

88

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

99

기본 개념 기본 개념

차수

 그래프 G 의 임의의 정점 v 를 끝점으로 하는 에지의 수

 deg(v) 표시

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1010

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1111

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1212

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1313

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1414

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1515

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1616

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1717

기본 개념 기본 개념

부분그래프 (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’ )

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1818

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

1919

기본 개념

기본 개념

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

2020

기본 개념

기본 개념

2121

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

오일러 경로 (Euler path)

 그래프 G=(V, E) 에 대해 G 안의 모든 정점과 모든 에지가 포함되는 경로

오일러 순환 (Euler cycle)

 그래프 G=(V, E) 에 대해 G 안의 모든 정점과 모든 에지가 포함되는 순환

오일러 그래프 (Euler graph)

 오일러 순환이 포함된 그래프

2222

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

2323

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

2424

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

2525

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

2626

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

해밀턴 경로 (Hamiltonian path)

 그래프 G=(V, E) 에 대해 G 안의 임의의 정점에서 출발하여 그래프의 각 정점이 한 번씩 만 나타나도록 만들어진 경로

해밀턴 순환 (Hamiltonian cycle)

 정점을 한 번씩만 지나고 다시 출발 정점으로 돌아오는 순환

해밀턴 그래프 (Hamiltonian graph)

 해밀턴 순환이 포함된 그래프

2727

Section 02 Section 02 Section 02

Section 02

오일러와 해밀턴 순환 오일러와 해밀턴 순환

[ 그림 8-4] 해밀턴 퍼즐의 그래프 [ 그림 8-5] 해밀턴 순환

해밀턴 퍼즐의 그래프

12 면체의 입체도형에 도시 이름을 주고 어떤 도시에서 출발하여

주어진 길을 따라 각 도시를 한 번만 방문하고 다시 출발 도시로

돌아오는 퍼즐

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

2828

여러 가지 그래프 여러 가지 그래프

평면그래프 (planer graph)

 그래프 G 를 평면에 그릴 때 어떤 에지도 정점이 아닌 곳에서는 교차하지 않 도록 그릴 수 있는 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

2929

여러 가지 그래프

여러 가지 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3030

여러 가지 그래프

여러 가지 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3131

여러 가지 그래프

여러 가지 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3232

여러 가지 그래프

여러 가지 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3333

여러 가지 그래프

여러 가지 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3434

여러 가지 그래프 여러 가지 그래프

[ 그림 8-6] 완전그래프

완전그래프 (complete graph)

 그래프 G 의 모든 정점들간에 서로 에지가 존재

 n 개의 정점을 가진 완전그래프를 K_n 으로 표시

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3535

여러 가지 그래프 여러 가지 그래프

[ 그림 8-7] 2- 정규그래프 , 3- 정규그래프 , 4- 정규그래프

정규그래프 (regular graph)

 그래프 G 의 모든 정점들이 같은 차수를 갖는 경우

k- 정규그래프

 차수가 k 인 정규그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3636

여러 가지 그래프 여러 가지 그래프

이분그래프 (bipartite graph)

 그래프 G 에서 정점의 집합 V 가 V = V₁∪V₂ 면서 V₁∩V₂ =Ø 을 만족 하는 두 집합 V₁ 과 V₂ 로 분리되고 , 그래프의 모든 에지가 V₁ 의 한 정점에 서 V₂ 의 한 정점으로 연결되는 그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3737

여러 가지 그래프 여러 가지 그래프

[ 그림 8-8] K_2,3,K_3,3 완전이분그래프

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

3838

여러 가지 그래프 여러 가지 그래프

[ 그림 8-9] 동형그래프

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

3939

그래프의 표현 그래프의 표현

otherwise E v

a

v



 

  ( , ) 0

1

인접행렬을 이용한 그래프 표현 방법

그래프 G 가 n 개의 정점을 갖는다고 하면 G 의 인접행렬은 nⅹ

행렬

이 인접행렬을 A=[a

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

4040

그래프의 표현

그래프의 표현

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

4141

그래프의 표현 그래프의 표현

인접리스트

인접행렬의 n 행들의 값을 n 개의 연결리스트로 표시

인접리스트 방식은 각 정점에 인접한 정점들을 일일이 열거하는 것 순서와 무관

필드 구성

 시작정점 : 헤드 (head)

 첫 번째 필드 : 정점

 두 번째 필드 : 링크 (link)

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

4242

그래프의 표현

그래프의 표현

4343

Section 05 Section 05 Section 05

Section 05

그래프 탐색 그래프 탐색

4444

Section 05 Section 05 Section 05

Section 05

그래프 탐색 그래프 탐색

4545

Section 05 Section 05 Section 05

Section 05

그래프 탐색 그래프 탐색

4646

Section 05 Section 05 Section 05

Section 05

그래프 탐색 그래프 탐색

IT CookBook IT CookBook IT CookBook IT CookBook

Thank you