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