[자료구조] MST는 MBST인가?

MST는 Minimum Spanning Tree로 그래프의 모든 정점을 연결하고(연결성분의 수가 1개이고), 간선의 개수가 정점 수 - 1개인 트리를 말한다.

MBST는 Minimum Battleneck Spanning Tree로, 트리를 이루는 간선의 최대 가중치가 최소가 되도록하는 스패닝트리를 말한다.

 

이번학기 자료구조 강의 내용에,

"MST는 MBST인가?"라는 내용에 대해서 교수님께서 설명을 해주셨는데,, 되게 짧게 설명을 해주셔서,,, 조금 보충하고자 이것저것 찾아봤는데, 한국어로 된 좋은 글이 없었어 이해하는 데에 애를 먹었다..

미래의 누군가가 나와 같은 고민을 하고있다면.. 이 글을 통해 해소할 수 있으면 좋겠다.

 

그래서 MST는 MBST일까?

어떤 그래프 G의 mst를 T, T의 bottleneck edge 즉, 최대 가중치 간선을 e라고 하고,

G의 mbst를 T', T'의 bottleneck edge를 e'이라고 하자.

T에서 e를 제거하면 두개의 연결성분으로 분리될 것이다. (n개의 정점을 이으려면 n-1개의 간선이 필요하니까!)

이때 두 연결성분을 각각 u와 v라고 하자. (정확히는 두 연결성분을 이루는 정점들의 집합을 각각 u와 v라고 하자..)

그래프 G의 모든 간선 중 u와 v를 연결하는 간선의 가중치는 반드시 e보다 크거나 같을 것이다. (만약 그렇지 않은 간선이 있다면, e를 빼고 해당 간선을 넣은게 mst가 되니까 T가 mst가 아니게 된다.)

그러므로 u, v를 연결하는 T'의 모든 간선이 e보다 크거나 같다. 즉, e <= (u,v를 잇는 T'의 모든간선)

여기서 T'의 간선들 중 최대 가중치 간선(bottleneck edge)이 e'이므로, 다음이 성립한다.

e <= (u,v를 잇는 T'의 모든 간선) <= e' . 따라서 e <= e' 이다.

또, T'은 G로 만들 수 있는 신장 트리 중 최소 병목 비용을 가지므로 e >= e' 또한 성립하게 된다.

위의 두 식에 의해서 e = e' 임이 증명 되었고, 따라서 MST는 MBST가 된다.

 

그럼 MBST는 MST일까?

결론은 '아니다'이다.

해당 그래프 G에 대해서, G의 최소신장트리는 간선 (1,2),(1,3)을 포함하고, 이때 최소병목비용은 2, 가중치 총합은 3이다.

하지만 간선(1,2),(2,3)을 포함하는 트리는 최소병목비용이 2인 MBST이지만, 간선의 총 합은 4로 최소신장트리는 아니다.