(1)최소 비용 신장 트리(MST) 기본이론

최소 비용 신장 트리(MST)

 

최소비용신장트리란

아래의 사진에서 각 노드들이 최소의 비용으로 모든 노드들이 연결되어야 하는 경우를 말한다. 

자세히 보면 무방향 가중치 그래프이다.  각 노드사이에 방향성은 없고 노드 사이에 가중치가 존재하는 형태이다. 

아래와 같은 사진을 보면 굵을 곡선으로 이루어진 트리가 최소비용신장트리이다. 

하지만 사진을 자세히 보면 알 수 있듯이 최소비용신장트리는 유일하지 않다. 만약 b와 c의 연결고리 대신 a와 h를 선택해도 같은 가중치에 모든 노드들이 연결되었을 것이다. 

 

위의 내용들을 정리해보자면 

 

• 무방향 가중치 그래프이다.
  
  
• 각 에지에 대한 가중치는 w(u, v)와 같이 표현가능하다. 
  
  
• 조건
  - T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다.
  - 가중치의 합이 최소가된다. 
  
  

왜 트리일까?

이전에 공부했던 이진 트리는 뭔가 나무를 거꿀로 한 것과 같은 모양이여서 좀 이해가 됐는데 이 친구는 트리같이 생기지도 않았으면서 왜 트리라고 부르는 것일까?? 

사실 트리에 대한 정의는 아래와 같이 정의된다. 

싸이클이 없는 연결된(Connected) 무방향 그래프를 트리라고 부른다. 모든 최소신장트리는 싸이클이 없다. 

왜 그런 것일까?? 

싸이클이 있다는 것은 각 노드들이 여러 경로를 통해 연결되어 있다는 것인데 최소 신장트리는 최소의 거리가 되는 경로만 선택하여 고르기 때문에 사이클이 만들어 질 수 없다. 

 

-> 그러므로 항상 트리가된다. 

**지나가는 팁**
인접과 연결의 차이

인접: 노드 사이에 엣지로 연결되어있다.
연결: 노드들을 통과하여 도달할 수 있으면 연결되어 있다고 한다.