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

1. 신장 트리 / 스패닝 트리 / 생성 나무 (Spanning Tree)

  ㅇ 노드 간 경로가 오직 하나 뿐인 토폴로지
     - 루프 순환이 없는 그래프의 일종
        . 즉, 모든 정점을 포함하나, 루프 순환(사이클)이 없는, 부분 그래프

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

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


2. 신장 트리 구조 (Spanning Tree Structure)

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

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

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