1. 신장 트리 / 스패닝 트리 / 생성 나무 (Spanning Tree)
ㅇ 노드 간 경로가 오직 하나 뿐인 토폴로지
- 루프 순환(looping, 예: Bridge Loop)이 없는 그래프의 일종으로써,
- 주로, 루프 순환의 방지를 위한 트리 특성을 갖는 그래프
※ [참고용어]
- 그래프 : 기하학적인 도형,구조,방정식,알고리즘의 설명,해석 등을 위한 시각적 표현 도구
- 트리 : 그래프의 특수한 경우로써, 순환이 없이 계층적인 구성이 가능함
- 토폴로지 : 외형적인 연결 모양/구조를 의미
- 루프 : 순환되는 경로
2. 신장 트리 구조 (Spanning Tree Structure)
ㅇ 무방향 그래프 G = (V,E)의 일종으로써,
- 비 순환 (Acyclic, 루프 순환이 없음) 이고, (★)
- 모든 노드들이 연결되어 있어야 하며,
- 간선 갯수가 |V|-1 개 임
* 임의 그래프로부터 만들 수 있는 신장 트리는, 매우 많음
ㅇ 사실상, 신장 트리 구조는,
- 최상의 정점(중심)을 루트 노드(root)로 하고,
- 모든 그룹 멤버들을 자손으로 갖는 `트리구조` 임
ㅇ 특징
- 모든 정점들의 연결에 끊임이 없어야 함
- (간선의 수 + 1) = (정점의 수)