그래프와 트리 (Graphs and Trees)

Presentation on theme: "그래프와 트리 (Graphs and Trees)"— Presentation transcript:

1 그래프와 트리 (Graphs and Trees)
이산수학(Discrete Mathematics) 그래프와 트리 (Graphs and Trees) 2016년 봄학기 강원대학교 컴퓨터과학전공 문양세

2 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)

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

4 용어 (Terminology) (1/2) Graphs and Trees 단순 그래프(simple graph): 각 에지는 서로 다른 두 노드를 연결하며, 같은 쌍의 노드를 연결하는 두 개의 에지는 존재하지 않는다. 다중 그래프(multigraph): 같은 쌍의 노드를 연결하는 다중 에지(multiple edges)가 존재한다.

5 용어 (Terminology) (2/2) 루프(loop): 노드 자기 자신을 연결하는 에지
Graphs and Trees 루프(loop): 노드 자기 자신을 연결하는 에지 의사 그래프(pseudo graph): 루프, 다중 에지를 포함하는 그래프이다.

6 방향성 그래프(Directed Graphs)
Graphs and Trees 지금까지 살펴본 그래프는 에지가 방향성을 갖지 않는 비방향성 그래프(undirected graph)이다. 방향성 그래프(directed graph, digraph): 그래프 G=(V,E)가 공집합이 아닌 노드들의 집합 V, 방향성 에지 혹은 아크(arcs)들의 집합 E로 구성된다. 각 에지는 노드의 순서쌍(ordered pair)이다. 단순 방향성 그래프(simple directed graph) 방향성 다중 그래프 (directed multigraph)

7 그래프 모델 (Graph Models) 그래프와 그래프 이론은 여러 모델에 이용될 수 있다.
Graphs and Trees 그래프와 그래프 이론은 여러 모델에 이용될 수 있다. 컴퓨터 네트워크 (Computer Networks) 소셜 네트워크 (Social Networks) 통신 네트워크 (Communication Networks) 정보 네트워크 (Information Networks) 소프트웨어 설계 (Software Design) 운송(교통) 네트워크 (Transportation Networks) 생물 네트워크 (Biological Networks)

8 그래프 모델 – 컴퓨터 네트워크 Graphs and Trees

9 그래프 모델 – 소셜 네트워크 (1/2) 소셜 네트워크 모델링
Graphs and Trees 소셜 네트워크 모델링 노드: 개인(individuals) 혹은 조직(organizations) 에지: 노드간의 관계(relationship) 교우관계 그래프(friendship graph): 두 사람이 친구이면 연결

10 그래프 모델 – 소셜 네트워크 (2/2) Graphs and Trees 영향력 그래프(influence graph): 한 사람이 다른 사람에게 영향력을 미침 (방향성 그래프) 협업 그래프(collaboration graph): 두 사람이 협력(공동연구) 하는 관계를 표시 (비방향성 그래프) 헐리우드 그래프: 두 배우가 공동 출연한 경우 연결 공동연구 그래프: 공저자인 경우 연결

11 전화 호출 그래프 Graphs and Trees

12 운송(교통) 네트워크 (1/2) Graphs and Trees 항공 네트워크 (Airline Network)

13 운송(교통) 네트워크 (2/2) Graphs and Trees 도로 네트워크 (Road Network)

14 생물 네트워크 (Biological Networks)
Graphs and Trees

15 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)

16 비방향성 그래프 (1/3) Graphs and Trees 정의: 비방향성 그래프 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로 계산한다.

17 비방향성 그래프 (2/3) Graphs and Trees 예제: 다음 그래프 G에서 노드의 이웃과 차수는?

18 비방향성 그래프 (3/3) Graphs and Trees 예제: 다음 그래프 H에서 노드의 이웃과 차수는?

19 방향성 그래프 (1/2) Graphs and Trees 정의: (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을 부여한다.

20 방향성 그래프 (2/2) 예제: 다음 그래프 G에서 노드의 입력 차수(in-degree)와 출력 차수(out-degree)는?
Graphs and Trees 예제: 다음 그래프 G에서 노드의 입력 차수(in-degree)와 출력 차수(out-degree)는?

21 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)

22 완전 그래프 (Complete Graphs)
Graphs and Trees 정의: 노드 n개에 대한 완전 그래프 Kn은 모든 노드간에 정확히 1개의 에지가 연결된 단순 그래프이다.

23 n-차원 큐브 (n-Dimensional Cube)
Graphs and Trees 정의: n-차원 큐브(or n-큐브) Qn은 길이 n의 2n개 비트 스트링을 나타내는 노드들을 갖는 그래프이다.

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

25 이분 그래프 예제 (1/3) Graphs and Trees C6는 이분 그래프인가? C6는 이분 그래프이다!  V1 = {v1, v3, v5}, V2 = {v2, v4, v6}

26 이분 그래프 예제 (2/3) Graphs and Trees C3는 이분 그래프인가? C3는 이분 그래프가 아니다!  C3를 공집합이 아닌 두 집합으로 구분하면, 적어도 한 집합은 두 노드를 포함하고, 이들 두 노드는 연결되어 있다.

27 이분 그래프 예제 (3/3) 그래프 H는 이분 그래프인가?
Graphs and Trees 그래프 H는 이분 그래프인가? H는 이분 그래프가 아니다!  노드 a, b, f가 C3를 형성하고 있는데, C3는 이분 그래프가 아니다.

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

29 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)

30 그래프의 표현 (Representation of Graphs)
Graphs and Trees 다음 그래프들을 어떻게 컴퓨터에서 표현할까? 즉, 컴퓨터에서 어떤 자료구조로 나타낼까?

31 인접 리스트 (Adjacent List) (1/2)
Graphs and Trees 인접 리스트(adjacent list): 각 노드에 대해 해당 노드에 인접한 다른 노드들을 리스트로 나열한다.

32 인접 리스트 (Adjacent List) (2/2)
Graphs and Trees 인접 리스트(adjacent list): 각 노드에 대해 해당 노드에 인접한 다른 노드들을 리스트로 나열한다.

33 인접 행렬 (Adjacent Matrix) (1/3)
Graphs and Trees 인접 행렬(adjacent matrix): 그래프 G=(V,E)에서 V={v1, v2, ..., vn}이라 할 때, G의 인접행렬 A=[aij]는 다음과 같이 정의된다. 단순 그래프의 인접행렬 예제

34 인접 행렬 (Adjacent Matrix) (2/3)
Graphs and Trees 다중 그래프의 인접행렬 예제

35 인접 행렬 (Adjacent Matrix) (3/3)
Graphs and Trees 가중치 방향성 그래프(weighted directed graph)의 인접행렬 v5 v1 v4 v2 v3 3 5 1 9 2 4

36 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)

37 트리(Tree)란? (1/2) Graphs and Trees 정의: 트리(tree)란 사이클(cycle, 순환)을 갖지 않는 연결된 비방향성 그래프(connected undirected graph)이다. 다음 중 트리는? YES YES NO NO

38 트리(Tree)란? (2/2) 정리: 비방향성 그래프가 트리라면 임의의 두 노드간의 경로는 유일하며, 그 역도 성립한다.
Graphs and Trees 정리: 비방향성 그래프가 트리라면 임의의 두 노드간의 경로는 유일하며, 그 역도 성립한다.

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

40 트리 모델링 (1/2) Graphs and Trees 파일 시스템의 디렉토리/파일 체계

41 트리 모델링 (2/2) Graphs and Trees 기업의 조직 체계

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

43 루티드 트리(Rooted Tree) (2/3)
Graphs and Trees 용어: 부모(parent), 자식(children), 형제(sibling)

44 루티드 트리(Rooted Tree) (3/3)
Graphs and Trees 용어: 조상(ancestor), 자손(descendant)

45 m-가지 트리(m-ary Tree) Graphs and Trees 정의: 트리의 모든 내부 노드가 m개 이하의 자식을 가질 경우, 이 트리를 m-가지 트리(m-ary tree)라 부른다. 또한, 모든 내부 노드가 정확히 m개 자식을 가질 경우 이를 전체 m-가지 트리(full m-ary tree)라 한다. 예제: 다음 중 전체 m-가지 트리인 것은?

46 이진 트리(Binary Tree) Graphs and Trees 정의: 트리의 모든 내부 노드가 최대 2개의 자식을 가지면 이를 이진 트리(binary tree)라 부른다. 이진 트리의 임의의 내부 노드가 두 자식을 가질 때, 첫 번째 자식을 왼쪽 자식(left child), 두 번째 지식을 오른쪽 자식(right child)라 한다. 왼쪽 자식을 루트로 하는 서브트리를 왼쪽 서브트리(left subtree), 오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브트리(right subtree)라 한다.

47 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology)
강의 내용 Graphs and Trees 그래프와 그래프 모델(Graphs and Graph Models) 그래프 용어 (Graph Terminology) 특별한 그래프 (Special Types of Graphs) 그래프 표현(Representing Graphs) 트리 소개 (Introduction to Trees)