Spanning Tree   스패닝 트리, 신장 트리, 생성 트리

(2023-11-03)

1. 신장 트리 / 스패닝 트리 / 생성 나무 (Spanning Tree)노드 간 경로가 오직 하나 뿐인 토폴로지
     - 루프 순환이 없는 그래프의 일종
        . 즉, 모든 정점을 포함하나, 루프 순환(사이클)이 없는, 부분 그래프

  ㅇ 주로, 루프 순환을 방지토록 트리 특성을 갖게 한 그래프
     - 주어진 그래프에서, 모든 정점간선 일부(또는, 전부)를 포함시키며, 루프 순환을 없앤 것

  ※ [참고용어]
     - 그래프 : 기하학적인 도형,구조,방정식,알고리즘의 설명,해석 등을 위한 시각적 표현 도구
     - 트리 : 그래프의 특수한 경우로써, 순환이 없이 계층적인 구성이 가능함
     - 토폴로지 : 외형적인 연결 모양/구조를 의미
     - 루프 : 순환되는 경로  例) 브리지 루프 (2 계층), 라우팅 루프 (3 계층)


2. 신장 트리 구조 (Spanning Tree Structure)무방향 그래프 G = (V,E)의 일종으로써,
     - 비 순환 (Acyclic, 루프 순환이 없음) 이고, (★)
     - 모든 노드들이 연결되어 있어야 하며, 
     - 간선 갯수가 |V|-1 개 임

  ㅇ 사실상, 신장 트리 구조는,
     - 최상의 정점(중심)을 루트 노드(root)로 하고, 
     - 모든 그룹 멤버들을 자손으로 갖는 `트리구조` 임

  ㅇ 특징 
     - 주어진 그래프에서, 모든 정점간선 일부(또는, 전부)를 포함
     - 루프순환(사이클) 없음
     - 모든 정점들의 연결에 끊임이 없어야 함
     - (간선의 수 + 1) = (정점의 수)
        . 즉, 정점 수 N 이면, 간선 수는 항상 N - 1 개임
     * 임의 그래프로부터 만들 수 있는 신장 트리는, 매우 많음

트리
   1. 트리   2. 트리 용어   3. 트리 종류   4. 트리 순회   5. 스패닝 트리   6. 이진 트리   7. 이진 트리 종류   8. 이진 탐색 트리   9. B 트리 (균형 트리)   10. 이진 힙   11. 멀티캐스트 트리   12. 결정 트리  
STP(Spanning Tree)
   1. STP(스패닝 트리 프로토콜)   2. BPDU   3. 루트 브리지   4. 브리지 ID   5. 스패닝 트리   6. 브리지 루프   7. 링크 비용  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"