트리의 개념

트리의 개념

1. 그래프 이론 방면 : 사이클이 없는 무향 연결그래프

 

2. 자료구조 방면 : 부모가 없는 루트노드부터 시작해서 여러 자식 노드로 방향이 있는 간선을 통해 뻗어 나가는 구조의 그래프. (부모가 없다는 것은 어떤 노드에서부터 시작해도 상관 없다는 뜻이다)

 

여기서 반드시 기억해야할 트리의 원칙 5가지를 제시한다

 

 1) 사이클이 없는 연결 그래프

 

 2) 정점의 수는 간선의 수보다 하나 많은 연결 그래프(V-E=1)

 

 3) 정점의 수는 간선의 수보다 하나 많으며, 사이클이 없는 그래프

 

 4) 어떤 두 노드를 골라도, 그 노드 사이의 단순 경로는 유일한 그래프

 

 5) 임의의 간선을 제거했을 때 연결 그래프가 아니게 되는 연결 그래프

 

다음 그림은 트리이다.

 

 

다음 그림은 트리가 아니다. 싸이클이 존재하기 때문이다