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. 링크 비용  


"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"