부분적 배낭 문제1 [알고리즘] ep6) 최소신장트리(MST) ㅁ가중그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게의 예: 거리, 비용, 시간 등 이 철도 그래프에서는 간선의 무게가 여행거리를 표현한다 신장 부그래프: 그래프 G의 모든 정점들을 포함하는 부그래프신장트리(spanning tree): 모든 정점이 다 이어져 있으면서, 싸이클이 없는 무방향 그래프 (자유 트리인 신장 부그래프)ㅇ최소신장트리(MST, Minimum Spanning Tree): 가중그래프의 총 간선 무게가 최소인 신장트리응용: 통신망, 교통망 [MST 속성 2가지] - MST 알고리즘 정확성 검증에 이용1. 싸이클 속성T를 가중그래프 G의 MST라 하자e를 T에 존재하지 않는 G의 간선으로, C를 T에 추가하여 형성된 싸이클로 가정그.. 2024. 7. 25. 이전 1 다음
