[이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘

[이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘(프림,크루스칼)

 

■ 신장 트리(Spanning Tree)란?

그래프 G의 꼭짓점을 모두 노드로 포함하는 트리 T

 

 

 

■ 최소신장 트리(Minimal Spanning Tree)란?

그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T

 

최소신장 트리를 구하기 위해서는 노드와 노드를 연결하는 변에 가중치가 부여된 그래프가 있어야 합니다. 또한 비용이 최소인 트리로 만들기 위한 알고리즘도 필요합니다. 

 

 

■ 최소신장 트리 구하는 알고리즘

 

프림 알고리즘(Prim Algorithm)

그래프 G의 변 중 비용이 가장 낮은 변들을 가지로 연결시켜서 트리로 만드는 알고리즘

▶프림 알고리즘 설명 더 보러가기

 

크루스칼 알고리즘(Kruskal Algorithm)

그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘

▶크루스칼 알고리즘 설명 더 보러가기

 

수학으로 이해하는 디지털 논리 이산수학 395p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------