그래프와 트리 (Graphs and Trees)

(1)

2016 년 봄학기 강원대학교 컴퓨터과학전공 문양세

이산수학 (Discrete Mathematics)

그래프와 트리

(Graphs and Trees)

(2)

Discrete Mathematics by Yang-Sae Moon

Page 2

강의 내용

그래프와 그래프 모델 (Graphs and Graph Models) 그래프 용어 (Graph Terminology)

특별한 그래프 (Special Types of Graphs) 그래프 표현 (Representing Graphs)

트리 소개 (Introduction to Trees)

Graphs and Trees

(3)

Page 3

그래프의 정의

정의 :

그래프 G = (V,E) 는 공집합이 아닌 노드 ( 정점 ) 들의 집합 V 와 에지 ( 이음선 ) 의 집합 E 로 구성된다 . 에지는 하나 혹은 두 개의 정점을 연 결한다 .

그래프 예제

Graphs and Trees

(4)

Page 4

용어 (Terminology) (1/2)

단순 그래프 (simple graph): 각 에지는 서로 다른 두 노드를 연결하며 , 같은 쌍의 노드를 연결하는 두 개의 에지는 존재하지 않는다 .

Graphs and Trees

다중 그래프 (multigraph):

같은 쌍의 노드를 연결하는 다중 에지 (multiple edges) 가 존재한다 .

(5)

Page 5

용어 (Terminology) (2/2)

루프 (loop): 노드 자기 자신을 연결하는 에지

Graphs and Trees

의사 그래프 (pseudo graph): 루프 , 다중 에지를 포함하는 그래프이다 .

(6)

Page 6

방향성 그래프 (Directed Graphs)

지금까지 살펴본 그래프는 에지가 방향성을 갖지 않는 비방향성 그래프 (undirected graph) 이다 .

방향성 그래프 (directed graph, digraph): 그래프 G=(V,E) 가 공집합이 아닌 노드들의 집합 V, 방향성 에지 혹은 아크 (arcs) 들의 집합 E 로 구 성된다 . 각 에지는 노드의 순서쌍 (ordered pair) 이다 .

 단순 방향성 그래프 (simple directed graph)

 방향성 다중 그래프 (directed multigraph)

Graphs and Trees

(7)

Page 7

그래프 모델 (Graph Models)

그래프와 그래프 이론은 여러 모델에 이용될 수 있다 .

 컴퓨터 네트워크 (Computer Networks)

 소셜 네트워크 (Social Networks)

 통신 네트워크 (Communication Networks)

 정보 네트워크 (Information Networks)

 소프트웨어 설계 (Software Design)

 운송 ( 교통 ) 네트워크 (Transportation Networks)

 생물 네트워크 (Biological Networks)

Graphs and Trees

(8)

Page 8

그래프 모델 – 컴퓨터 네트워크

Graphs and Trees

(9)

Page 9

그래프 모델 – 소셜 네트워크 (1/2)

소셜 네트워크 모델링

 노드 : 개인 (individuals) 혹은 조직 (organizations)

 에지 : 노드간의 관계 (relationship)

교우관계 그래프 (friendship graph): 두 사람이 친구이면 연결

Graphs and Trees

(10)

Page 10

그래프 모델 – 소셜 네트워크 (2/2)

영향력 그래프 (influence graph):

한 사람이 다른 사람에게 영향력을 미침 ( 방향성 그래프 )

Graphs and Trees

협업 그래프 (collaboration graph):

두 사람이 협력 ( 공동연구 ) 하는 관계를 표시 ( 비방향성 그래프 )

 헐리우드 그래프 : 두 배우가 공동 출연한 경우 연결

 공동연구 그래프 : 공저자인 경우 연결

(11)

Page 11

전화 호출 그래프

Graphs and Trees

(12)

Page 12

운송 ( 교통 ) 네트워크 (1/2)

Graphs and Trees

항공 네트워크 (Airline Network)

(13)

Page 13

운송 ( 교통 ) 네트워크 (2/2)

Graphs and Trees

도로 네트워크 (Road Network)

(14)

Page 14

생물 네트워크 (Biological Networks)

Graphs and Trees

(15)

Page 15

강의 내용

그래프와 그래프 모델 (Graphs and Graph Models) 그래프 용어 (Graph Terminology)

특별한 그래프 (Special Types of Graphs) 그래프 표현 (Representing Graphs)

트리 소개 (Introduction to Trees)

Graphs and Trees

(16)

Page 16

비방향성 그래프 (1/3)

정의 : 비방향성 그래프 G 에서 두 노드 u, v 가 에지 e 로 연결되어 있 다면 , u 와 v 는 인접 (adjacent) 하다 혹은 이웃 (neighbor) 한다고 한 다 . 이때 , 에지 e 가 노드 u 와 v 를 연결 (connect) 한다고 한다 .

정의 : G=(V,E) 의 한 노드 v 의 모든 이웃의 집합을

v

의 이웃이라 하고 ,

N(v)

라 표기한다 . 또한 , A 가 V 의 부분집합이라면

N(A)

는 A 내 노드 에 인접한 모든 노드들의 집합이다 .

정의 : 노드의 차수 (degree of a node, degree of a vertex) 란 해당 노드 에 연결된 에지의 수를 나타내며 , deg(v) 라 표기한다 . 루프의 경우 차 수 2 로 계산한다 .

Graphs and Trees

(17)

Page 17

비방향성 그래프 (2/3)

예제 : 다음 그래프 G 에서 노드의 이웃과 차수는 ?

Graphs and Trees

(18)

Page 18

비방향성 그래프 (3/3)

예제 : 다음 그래프 H 에서 노드의 이웃과 차수는 ?

Graphs and Trees

(19)

Page 19

방향성 그래프 (1/2)

정의 : (u,v) 가 방향성 그래프 G 의 에지 e 라 할 때 , e 는 v 로 인접

(adjacent to) 한다 혹은 e 는 u 로 부터 인접 (adjacent from) 한다고 한 다 . 이때 , u 를 시작 노드 (initial node) 라 하고 v 를 종료 노드

(terminal node) 라 한다 .

정의 : 노드 v 의 입력 차수 (in-degree) 란 v 를 종료 노드로 하는 에지 의 수이며 , deg^(v) 라 표기한다 . 반대로 , 노드 v 의 출력 차수 (out- degree) 란

v

를 시작 노드로 하는 에지의 수이며 , deg⁺(v) 라 표기한다 .

 참고 : 루프의 경우 , 입력 차수에 1, 출력 차수에 1 을 부여한다 .

Graphs and Trees

(20)

Page 20

방향성 그래프 (2/2)

Graphs and Trees

예제 : 다음 그래프 G 에서 노드의 입력 차수 (in-degree) 와 출력 차수 (out-degree) 는 ?

(21)

Page 21

강의 내용

그래프와 그래프 모델 (Graphs and Graph Models) 그래프 용어 (Graph Terminology)

특별한 그래프 (Special Types of Graphs) 그래프 표현 (Representing Graphs)

트리 소개 (Introduction to Trees)

Graphs and Trees

(22)

Page 22

완전 그래프 (Complete Graphs)

정의 : 노드 n 개에 대한 완전 그래프 K_n 은 모든 노드간에 정확히 1 개 의 에지가 연결된 단순 그래프이다 .

Graphs and Trees

(23)

Page 23

n- 차원 큐브 (n-Dimensional Cube)

정의 :

n-

차원 큐브 (or n- 큐브 ) Q_n 은 길이 n 의 2ⁿ 개 비트 스트링을 나 타내는 노드들을 갖는 그래프이다 .

Graphs and Trees

(24)

Page 24

이분 그래프 (Bipartite Graphs)

정의 : 단순 그래프 G=(V,E) 에서 , 집합 V 가 서로 소 (disjoint) 인 두 집 합 V₁, V₂ 로 분리되고 , E 의 모든 에지는 V₁ 의 한 노드와 V₂ 의 한 노드 를 연결하면 , G 는 이분 (bipartite) 되었다고 한다 .

Graphs and Trees

(25)

Page 25

이분 그래프 예제 (1/3)

C

₆ 는 이분 그래프인가 ?

Graphs and Trees

C

₆ 는 이분 그래프이다 !

 V₁ = {v₁, v₃, v₅}, V2 = {v₂, v₄, v₆}

(26)

Page 26

이분 그래프 예제 (2/3)

C

₃ 는 이분 그래프인가 ?

Graphs and Trees

C

₃ 는 이분 그래프가 아니다 !

 C₃ 를 공집합이 아닌 두 집합으로 구분하면 ,

적어도 한 집합은 두 노드를 포함하고 , 이들 두 노드는 연결되어 있 다 .

(27)

Page 27

이분 그래프 예제 (3/3)

그래프 H 는 이분 그래프인가 ?

Graphs and Trees

H

는 이분 그래프가 아니다 !

 노드 a, b, f 가 C₃ 를 형성하고 있는데 , C₃ 는 이분 그래프가 아니다 .

(28)

Page 28

서브그래프 (Subgraphs)

정의 : 그래프 G=(V,E) 에서 , WV, FE 를 만족하는 W 와 F 로 구성된 그래프 (W,F) 를 G 의 서브그래프라 정의한다 .

Graphs and Trees

(29)

Page 29

강의 내용

그래프와 그래프 모델 (Graphs and Graph Models) 그래프 용어 (Graph Terminology)

특별한 그래프 (Special Types of Graphs) 그래프 표현 (Representing Graphs)

트리 소개 (Introduction to Trees)

Graphs and Trees

(30)

Page 30

그래프의 표현 (Representation of Graphs)

다음 그래프들을 어떻게 컴퓨터에서 표현할까 ? 즉 , 컴퓨터에서 어떤 자료구조로 나타낼까 ?

Graphs and Trees

(31)

Page 31

인접 리스트 (Adjacent List) (1/2)

인접 리스트 (adjacent list):

각 노드에 대해 해당 노드에 인접한 다른 노드들을 리스트로 나열한다 .

Graphs and Trees

(32)

Page 32

인접 리스트 (Adjacent List) (2/2)

인접 리스트 (adjacent list):

각 노드에 대해 해당 노드에 인접한 다른 노드들을 리스트로 나열한다 .

Graphs and Trees

(33)

Page 33

인접 행렬 (Adjacent Matrix) (1/3)

인접 행렬 (adjacent matrix):

그래프 G=(V,E) 에서 V={v₁, v₂, ..., v_n} 이라 할 때 , G 의 인접행렬

A=[a

_ij] 는 다음과 같이 정의된다 .

Graphs and Trees

단순 그래프의 인접행렬 예제

(34)

Page 34

인접 행렬 (Adjacent Matrix) (2/3)

Graphs and Trees

다중 그래프의 인접행렬 예제

(35)

Page 35

인접 행렬 (Adjacent Matrix) (3/3)

Graphs and Trees

가중치 방향성 그래프 (weighted directed graph) 의 인접행렬

v

₅

v

₁

v

₄

v

₂

v

₃

3

5 1 9

1 2

3 2

3

4 [ ][ ] 1 2 3 4 5 1 0 1 1 5 2 9 0 3 2

3 0 4

4 2 0 3

5 3 0

W i j



  

 

  

[ ][ ]

0

i j

v v

W i j v v

i j



 

 



에서로가는이음선이있는경우 가중치

에서로가는이음선이없는경우 인경우

(36)

Page 36

강의 내용

그래프와 그래프 모델 (Graphs and Graph Models) 그래프 용어 (Graph Terminology)

특별한 그래프 (Special Types of Graphs) 그래프 표현 (Representing Graphs)

트리 소개 (Introduction to Trees)

Graphs and Trees

(37)

Page 37

트리 (Tree) 란 ? (1/2)

정의 : 트리 (tree) 란 사이클 (cycle, 순환 ) 을 갖지 않는 연결된 비방향 성 그래프 (connected undirected graph) 이다 .

다음 중 트리는 ?

Graphs and Trees

YES YES NO NO

(38)

Page 38

트리 (Tree) 란 ? (2/2)

정리 : 비방향성 그래프가 트리라면 임의의 두 노드간의 경로는 유일하 며 , 그 역도 성립한다 .

Graphs and Trees

(39)

Page 39

포레스트 (Forest) 란 ?

정의 : 한 개 이상의 트리로 구성된 그래프를 포레스트 (forest) 라 한다 . 즉 , 트리들의 집합을 포레스트라 부른다 .

Graphs and Trees

(40)

Page 40

트리 모델링 (1/2)

파일 시스템의 디렉토리 / 파일 체계

Graphs and Trees

(41)

Page 41

트리 모델링 (2/2)

기업의 조직 체계

Graphs and Trees

(42)

Page 42

루티드 트리 (Rooted Tree) (1/3)

정의 : 트리에서 하나의 노드가 루트 (root) 로 지정된 경우 이를 루티드 트리 (rooted tree) 라 정의한다 . 루트를 제외한 모든 노드는 루트로부 터 뻗어서 연결된다 .

Graphs and Trees

(43)

Page 43

루티드 트리 (Rooted Tree) (2/3)

용어 : 부모 (parent), 자식 (children), 형제 (sibling)

Graphs and Trees

(44)

Page 44

루티드 트리 (Rooted Tree) (3/3)

용어 : 조상 (ancestor), 자손 (descendant)

Graphs and Trees

(45)

Page 45

m- 가지 트리 (m-ary Tree)

정의 : 트리의 모든 내부 노드가 m 개 이하의 자식을 가질 경우 , 이 트 리를

m-

가지 트리 (m-ary tree) 라 부른다 . 또한 , 모든 내부 노드가 정 확히 m 개 자식을 가질 경우 이를 전체 m- 가지 트리 (full m-ary tree) 라 한다 .

예제 : 다음 중 전체 m- 가지 트리인 것은 ?

Graphs and Trees

(46)

Page 46

이진 트리 (Binary Tree)

정의 : 트리의 모든 내부 노드가 최대 2 개의 자식을 가지면 이를 이진 트리 (binary tree) 라 부른다 .

 이진 트리의 임의의 내부 노드가 두 자식을 가질 때 , 첫 번째 자식을 왼쪽 자식 (left

child),

두 번째 지식을 오른쪽 자식 (right child) 라 한다 .

 왼쪽 자식을 루트로 하는 서브트리를 왼쪽 서브트리 (left subtree),

오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브트리 (right subtree) 라 한다 .

Graphs and Trees

(47)