그래프 - 최소신장트리(Minimum spanning tree)??

안녕하세요~
오늘도 찾아왔습니다.
오늘은 굉장히 아주 굉장히 짧을 것 같습니다.

오늘은 저번에 말씀드린대로 최소신장트리(Minimum spanning tree)에 대해서 알아보고자 합니다.
저번시간에 신장트리에 대해서 말씀드렸었죠?
신장트리는 쉽게 말해 모든 정점을 연결한 트리를 말하는 것이지요? 연결을 최소로 한...

자 그럼 오늘 할 최소신장트리란 무엇인가?
신장트리에 최소가 들어갔네요.
음, 간단하게 해석하면 신장트리를 최소로 한다라고 할 수 있겠네요...
그런데 뭘 최소로 하는 걸까요?

여러분 지하철 타 보셨죠? 지하철로 예를 들어볼까요?
음 지하철을 타고 어떠한 지점에 간다고 할 때 최소한의 역을 통과해서 원하는 역에 도착할 수 있지요?
그런데 만약 다양한 길이 존재할 때 똑같은 정거장 수라도 가는 거리에 따라 걸리는 시간이 다르지요?
물론 약간 다른 예이긴 하지만요.

최소신장트리란 무엇인가?
지금까지 생각했던 신장트리는 어떤 간선이든 같은 것이라고 생각했지요? 물론 설명에도 별말이 없었고요.
하지만 그러한 간선에 가중치라는 것을 대입을 한다면 신장트리에 종류에 따라 다양한 총 가중치가 나오겠지요?
가중치라는 것은 쉽게 생각해서 걸리는 시간 정도로 생각하시면 편해요.

음 간단하게 예를 들어보지요.

저번에 했던 그래프를 예로 들어보죠. 옆에 써있는 빨간 숫자들이 가중치라고 하지요.

네~ 양쪽 모두 저번시간에 봤던데로 신장트리입니다.
하지만 왼쪽과 오른쪽은 가중치가 다르지요?
결국 총 가중치가 달라집니다. 왼쪽은 6, 오른쪽은 12네요.
오른쪽이 왼쪽보다 2배의 가중치가 드네요.

이처럼 각각에 가중치가 존재할 때 어떻하면 좀 더 적은 가중치로 신장트리를 구현하는 것이지요.
그것이 바로 최소신장트리입니다.
최소신장트리도 신장트리와 마찬가지로 사이클이 없어야 합니다. 뭐 트리니까요.
또한 최소의 간선을 연결하므로 결국 정점보다 하나 적은 갯수입니다.

최소신장트리를 구하는 방법이 몇가지가 있는데요.
그건 다음 포스트에 쓰도록 하겠습니다.
오타나 잘못된 부분은 지적해주심 감사하겠습니다~
그럼 다음 포스트 때 뵈요~