[강의노트] 최소신장트리 - 1

최소신장트리 - 1

 

가중그래프

간선에 무게를 가지는 그래프. 이미 배운 내용이라 익숙하다.

아래 가중그래프 예시를 보면, 각 지역(정점)을 잇는 간선의 무게는 여행거리(km)를 나타낸다.

 

신장트리 

신장 부그래프를 다시 떠올려보면 , 모든 정점 + 부분간선의 그래프라고 외웠었다. 그 중에서 트리인 그래프를

우리는 신장트리라고 부른다.  다시 말하면, 신장트리(Spanning Tree)는 그래프가 있을 때 모든 노드를 포함하면서

사이클이 존재하지 않는 부분 그래프를 의미한다.

 

그림은 그래프 G의 노드 A,B,C를 모두 포함하지만 순환이 존재하지않는 그래프 G의 신장트리 3개를 보여주고 있다.

 

그럼 최소신장트리는 무엇일까? 

최소신장트리는 신장트리 중에서 총 간선 무게의 합이 최소인 신장트리를 의미한다. 

 

 

최소신장트리

방금 살펴보았던 가중그래프예시에 최소신장트리를 구해보자.

 

위의 그래프의 신장트리는 여러가지가 존재하겠지만, 그중 최소신장트리는 위에 빨간색 간선만을 채택하는 신장트리가 된다.  

 

이러한 최소신장트리는 다양하게 응용될 수 있는데 한가지 예시를 들어보면,

그래프에 존재하는 모든 지역을 탐방해야하는데 어떤 순서로 탐방해야 가장 기름값을 절약할 수 있을까? 와 같은 문제를 해결할 수 있다.

 

 

최소신장트리의 속성

최소신장트리의 속성에는 싸이클 속성과 분할 속성이 있다.

먼저 싸이클속성을 알아보자.

 

싸이클 속성

빨간색 간선으로 연결된 트리 T는 그래프의 최소신장트리이다.

이때 싸이클을 만드는 간선 e를 추가해서 싸이클 C을 만든다.

그러면 싸이클 C의 모든 간선들 f에 대해

weight(f) <= weight(e) 를 만족한다.

즉 싸이클의 어떠한 간선을 골라도 새로 추가한 간선 e가 더 가중치가 크다는 말이다.

 

증명은 모순법을 통해 간단하게 증명할 수 있다.

싸이클을 만드는 간선 e의 가중치보다 싸이클에 어떠한 간선 f의 가중치가 더 크다면, 

f를 삭제하고, e를 채택해서 만든 신장트리가 더 가중치가 낮게 된다.

따라서 처음에 트리T는 최소신장트리다 라는 가정과 모순이 발생한다.

 

분할 속성

 

위의 그림을 보자. 빨간색간선으로 연결된 것은 최소신장트리이다.

하지만 두개의 분할 그룹을 간선 f가 연결하고 있는 구조를 보이는데, 간선 e와 f가 가중치가 같기때문에

간선 f대신 e를 채택해도 최소신장트리가 된다.

즉 최소신장트리는 항상 하나만 존재하는 것이 아니라, 여러개가 존재할 수도 있다는것이다.

이 사실을 먼저 기억하고 분할 속성을 살펴보자.

 

그래프에 존재하는 정점들을 두 개의 부분집합 U와 V로 분할한다고 하자.

그림과 같이 U와 V로 분할되었을때, 분할을 가로지르는 최소 가중치 간선을 e라고 하자.

 

이때 간선 e를 포함하는 G의 최소신장트리가 반드시 존재한다는 특성이다. 

최소신장트리는 두 분할을 무조건 연결해야하고,  분할을 연결하는 간선들 중 최소 가중치 간선을 채택해야하는 것은

당연하기때문에 받아들이기 어렵지않다고 생각했다. 

 

한번 증명을 읽어보자.

T를 최소신장트리라하자.

만약 T가 간선 e를 포함하지않는다면, e를 T에 추가하여 형성된 싸이클 C를 구성하는 간선들 가운데

분할을 가로지르는 간선 f가 존재한다.

 

아까 증명한 싸이클 속성에 의해

weight(f) <= weight(e) 이므로, f를 e로 대체하면 또 하나의 최소신장트리를 얻을 수 있다.

( e는 최소무게 간선이므로, weight(f) = weight(e) 이다)

 

별로 어렵지 않게 이해할 수 있었다.

 

 

다음은 최소신장트리 알고리즘을 다루기전에, 알고리즘이 취하고 있는 기법인 탐욕법(그리디 메소드)를 알아보자.

 

탐욕법

https://man-25-1.tistory.com/142

그리디 알고리즘

예전에 그리디 알고리즘에 대해서 한번 공부한적이 있었다.

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

+ 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있어야함.

+ 그리디 해법은 그 정당성 분석이 중요하다.

 

  이 과정에서 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

 

 

첫번째로 알아볼 탐욕법 예시는 잔돈 거스르기 문제이다.

"만약 이 문제가 탐욕적 선택 속성을 가졌다면 탐욕해는 최적해가 된다."

위의 말이 무슨 뜻일까? 탐욕적 선택 속성을 가진 문제에 대해서만 그리디 알고리즘을 사용할 수 있다고 한다.

 

탐욕법은 매 순간 단순히 가장 좋은 방법을 채택한다.

예시 1,2번이 탐욕적 선택 속성을 쉽게 설명해주고 있는데, 2번 예시에서 탐욕법을 적용하면 40원을 만들기 위해

30원을 사용하게되고, 10원이 남았기때문에 5원동전 2개를 사용해서 총 3개의 동전을 택하게 된다.

하지만 최적해는 2개이다.

 

즉 일반화하면 거스름돈 문제에서 가장 큰 화폐단위부터 돈을 거슬러주는 아이디어는 가지고 있는 동전이 큰 단위가 작은 단위의 배수인 경우에만 정당성이 보장된다는 뜻이다.

 

두번째로 알아볼 탐욕법 예시는 부분적 배낭 문제이다.

가장 가치가 높은 B를 넣고, A를 넣으면 최적해인 43의 이득이 나온다.

위와 비슷하지만 탐욕적 속성이 없는 배낭문제가 있다.

0-1 배낭 문제는 아까 액체 용기처럼 원하는 만큼을 취할 수 없고, 무조건 취하거나 취하지않거나 ( 0 과 1)의 문제이다

따라서 탐욕적 선택 속성을 만족하지 않는다.

탐욕법에 따라, 가치가 가장 높은 B를 먼저 담게되면, 배낭에 7키로 공간이 남으므로 A와 C는 고려할 수 없다

따라서 D와 E를 하나씩 취하게되는데 B,D,E에 대한 탐욕해는 24이다. 하지만 최적해는 36 이므로, 탐욕적 선택 속성을 만족하지 않는 것이 확인된다.

 

다음 포스트에서는 아래 세개의 알고리즘을 배워보자.