'2020/12 글 목록

_Spanning Tree 정의 Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다. 원래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결되어 있음 트리의 속성을 만족 ( 사이클이 존재하지 않음) 즉, 그래프의 최소 연결 부분 그래프이다. 최소 연결 = 간선의 수가 가장 적다 N개의 노드를 가진 그래프 최소 간선의 수 : N-1 (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree _Minimum Spanning Tree (MST) 가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree 위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다. 두번째, 세번째 트리가 모두 가중치의 합이..