* 용어 설명
- 위의 그래프 G1은 무방향 가중치 연결 그래프를 나타내고 있다.
- 순환경로(cycle) : 시작하는 정점과 끝나는 정점이 같은 것
※ 여기서 경로란? 한 정점에서 다른 정점으로 가는 길을 말한다.
- 부분그래프 : 그래프 중에서 일부분을 나타낸 것
- 트리 : 연결 되어 있고 순환 경로가 없는 그래프
- 신장트리 : 그래프의 부분 그래프 중에서 본래 그래프의 모든 정점을
가지고 있으며, 트리가 되는 것
- 최소비용 신장 트리: 신장트리들 중에서 가중치가 가장 적은 트리
* 무작정 알고리즘
- 모든 신장트리를 고려한 후, 그 중에서 비용이 가장 적게되는 것을 선택
- 분석 : 각 간선은 포함 될수도 있고 안될 수도 있다.(각간선마다 2가지 경우가 존재한다.)
> 2 * 2 * 2 * ... * 2 = 2^n ∈ 세타의 n^2
* 탐욕적 알고리즘
- 전략 : 트리에 추가할 연결선들을 반복적으로 선택한다.
( 한 연결선이 좋은지를 쉽게 판단가능 하다 )
- 한 연결선이 선택되면 그 연결선의 종점들을 합친다.
ex)
> 여기서 3과 4를 선택한 것은 좋을 수도 있고 나쁠 수도 있다.
- 탐욕적 알고리즘을 적용하기 적절한 이유
> 정점 a와 b가 연결된다면, 정점 a에 연결하는 것은 정점 b에 연결하는 것과 같다.
> 즉, a와 b가 연결되있다는 것은 다른 정점에서 a에 갈 수 있다는 것은 b로도 갈수 있다는 것이고,
이의 역인 다른 정점에서 b로 갈수 있다는 것은 a로도 갈수 있다는 이야기이다.
- 사용할 사실(명제)
> 한 그래프 G는 (n-1)개의 연결선들을 가지고, 순환 경로가 없으면 트리라고 할수 있다.
> 또한 G가 트리이면 그 안에 (n-1)개의 연결선들이 있고, 비순환그래프이다.
- 명제 정리
> 연결선 e가 정점 v에 접합한 가장 가벼운 (가중치가 작은) 연결선이라고 하자.
그러면 e를 포함하는 최소비용 신장 트리가 있다고 할 수 있다.
- 전략
> 종점 지향 전략 (Prim의 알고리즘)
- 처음 시작할 때 임의의 한 정점 V0를 선택한다.
- V0에서 나가는 가장 가벼운 연결선을 선택한다. 그 연결선이 (V0, x)라고하면 그것을 최소신장 트리 T에
추가를 하고 V0와 x를 합친다. 모든 정점이 T에 포함될때까지 이 과정을 반복한다.
ex) 다음의 최소 신장 트리를 구하여라
ⓐ V1에서 시작한다.
ⓑ V2가 V1에서 가장 가까으므로 V2를 선택한다.
ⓒ V3가 {V1,V2}에서 가장 가까으므로 V3를 선택한다.
연결선 (V1,V3)와 (V2,V3)의 가중치가 같으므로 아무것이나
선택한다.(V1,V3)을 선택하기로 한다.
ⓓ V5가 {V1,V2,V3}에 가장 가까우므로 V5를 선택한다.
ⓔ V4를 선택한다. 연결선 (V3,V4)가 가장 가까우므로 T에 추가한다.
> 최소신장 트리가 만들어 졌다.
> 다음 그림은 과정별로 나타나는 최소신장트리와 그래프의 변화이다.
> 연결선 지향 전략 (Kruskal의 알고리즘)
- 그래프에 남아 있는 가장 가벼운 연결선을 선택한다.
- 선택된 연결선이 통합된 두 개의 정점들 사이에 있다면 버린다. 아니면 T에 추가한다.
ex) 다음의 최소 신장 트리를 구하여라
ⓐ 연결선들을 가중치에 의해 정렬한다.
ⓑ 연결선 (V1,V2)가 가장 가까우므로 선택한다.
ⓒ 연결선 (V3,V5)가 가장 가까우므로 선택한다.
ⓓ 연결선 (V1,V3)와 (V2,V3)가 가장 가까우므로 둘중에 하나를
선택한다. (V1,V3)를 선택했다.
ⓔ 연결선 (V3,V4)가 가장 가벼우므로 선택한다.
> 다음 그림은 과정별로 나타나는 최소신장트리와 그래프의 변화이다.
