[이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등)_예제포함

[이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등)

 

■ 트리(Tree)

- 트리 T는 비순환, 연결 그래프

- 루트(Root)라고 불리는 노드가 반드시 하나 있어야 함

- 트리 T를 구성하는 꼭짓점 v, w 간에, v에서 w로 가는 단순 경로가 있음

 

▶ 선형과 비선형, 순환과 비순환의 뜻은?

 

■ 서브 트리(Sub Tree)

- T를 구성하는 꼭짓점 v를 루트로 하는 트리

 

 

예제

다음 중 트리인 것은?

풀이

예제풀이

(1) A가 루트며 그래프를 구성하는 꼭짓점 A부터 G 사이에는 단순 경로만 존재하므로 트리다.

(2) A-B-D 간에 순환 경로가 존재하고, A-B-D와 C-E가 연결되지 있지 않으므로 비연결 그래프다. 그러므로 트리가 아니다.  

---

 

아래 트리(Tree)로 관련 용어를 설명하겠습니다. 

 

 

 

 

■ 노드(Node)

- 그래프 T를 구성하는 꼭짓점

A , B, C, D, E, F, G, H, I. J, K, L, M

 

■ 루트(Root)

- 그래프 T의 시작 노드, 그래프 T의 가장 높은 곳에 위치

A

 

■ 부모 노드(Parent Node)

- 어떤 노드이 한 단계 상위 노드

A: B와 C의 부노 노드

B: E, D, F의 부모 노드

C: G의 부모 노드

D: H, I의 부모 노드

G: J, K, L의 부모 노드

I, M의 부모 노드

 

■ 자식 노드(Child Node)

- 어떤 노드의 한 단계 하위 노드

B, C: A의 자식 노드

D, E, F: B의 자식 노드

G: C의 자식 노드

H, I: D의 자식 노드

J, K, L: G의 자식 노드

M: I의 자식 노드

 

■ 형제 노드(Sibling Node)

- 같은 단계에 있으면서 부모가 같은 노드들

B의 형제 노드: C

C의 형제 노드: B

E의 형제 노드: E, F

F의 형제 노드: D, F

G의 형제 노드: D, E

H의 형제 노드: I

I의 형제 노드: H

J의 형제 노드: K, L

L의 형제 노드: J, L

K의 형제 노드: J, K

 

■ 잎 노드(Leaf Node)

- 자식 노드가 없는 노드

H, M, E, F, J, K, L

 

■ 중간 노드(Internal Node)

- 루트 노드나 잎 노드가 아닌 노드

B, C, D, G, I

 

■ 조상 노드(Ancestor Node)

- 루트 노드에서 어떤 노드에 이르는 경로에 포함된 모든 노드 

M의 조상 노드: I, D, B, A

G의 조상 노드: C, A

F의 조상 노드: B, A

L의 조상 노드: G, C, A

 

■ 자손 노드(Descendant Node)

- 어떤 노드에서 잎 노드에 이르는 경로에 포함된 모든 노드

A의 자손 노드: B, C, D, E, F, G, H, I. J, K, L, M

B의 자손 노드: D, E, F, H, I.,M

C의 자손 노드:  G, J, K, L

D의 자손 노드: H, I, M

I의 자손 노드: M

 

■ 차수(Degree)

- 어떤 노드에 포함된 자식 노드의 개수

A의 차수: 2  ∵ A의 자식 노드 B, C

B의 차수: 2  ∵ B의 자식 노드 D, E, F

C의 차수: 2  ∵ C의 자식 노드 G

D의 차수: 2  ∵ D의 자식 노드 H, I

E의 차수: 2  ∵ E의 자식 노드는 없음 

F의 차수: 2  ∵ F의 자식 노드는 없음 

G의 차수: 2  ∵ G의 자식 노드 J, K, L

H의 차수: 2  ∵ H의 자식 노드는 없음 

I의 차수: 2  ∵ I의 자식 노드 M

J의 차수: 2  ∵ J의 자식 노드는 없음 

K의 차수: 2  ∵ K의 자식 노드는 없음 

L의 차수: 2  ∵ L의 자식 노드는 없음 

M의 차수: 2  ∵ M의 자식 노드는 없음 

 

■ 레벨(Level)

- 루트 노드를 0으로 시작하여, 자식 노드로 내려갈 때마다 하나씩 증가하는 단계

레벨 0에 속하는 노드: A

레벨 0에 속하는 노드: B, C

레벨 0에 속하는 노드: D, E, F, G

레벨 0에 속하는 노드: H, I, J, K, L

레벨 0에 속하는 노드: M

 

■ 트리의 높이(Height)/ 트리의 깊이(Depth)  

- 트리가 가지는 최대 레벨

트리의 높이(깊이) 4

 

■ 숲(Forest)

- 루트 노드를 제거하여 얻는 서브 트리의 집합

B, C를 루트로 하는 서브 트리

 

수학으로 이해하는 디지털 논리 이산수학 352-357p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------