Kruskal 알고리즘 증명

Kruskal 알고리즘 증명

보조정리
G(V.E)는 연결된 가중치 포함 비방향 그래프, F는 E의 유망한 부분집합, e는 F∪{e}하여 순환이 생기지 않도록 해서 E-F에 속한 최소 가중치 이음선이라 하자. 그러면 F∪{e}는 유망하다.
증명:F가 유망하기 때문에 다음식을 만족하는 이음선의 집합 F'이 존재해야 하고
F⊆F'
(V,F')는 최소비용 신장 트리이어야 한다. 만약 e∈F'인 경우,
F∪{e}⊆F'
이는
F∪{e}임을 의미하고, 따라서 증명되었다.
그렇지 않은 경우,(V.F')가 신장트리이므로, F'∪{e}는 정확하게 순환을 하나 포함하고 있어야 하며, e가 바로 그 순환이어야 한다.
그런데 F∪{e}에는 순환이 없으므로, 그 순환에 속한 어떤 이음선 e'∈F'가 존재해야 하고, 그 이음선은 F에 속하지 않는다. 즉, e'∈E-F가 된다. 집합 F'∪{e'} 에는 F'의 부분 집합이므로 단순순환이 존재하지 않는다. 그러므로 E의 가중치는 e'의 가중치보다 크지 않다.
F'∪{e}에서 e'을 제거 하면, 이 집합에서 순환은 없어지며, 이는 신장 트리가 됨을 뜻한다. 실제로 다음 집합은 최소비용 신장트리가 된다.
F'∪{e}-{e'}
왜냐하면 위에서 보여준 대로 e의 가중치는 e'의 가중치보다 크지 않기 때문이다. e'가 F에 속하지 않으므로, 다음과 같다.
F∪{e}⊆F'∪{e}-{e}
따라서 F∪{e}는 유망하다.

크루스칼 알고리즘은 항상 최소비용 신장트리를 만들어 낸다.
증명 : 귀납법을 이용하여 While 루프가 수행후 집합 F가 유망한것을 증명한다.
귀납출발점 : 공집합은 당연히 유망하다.
귀납가정 : while 루프에서 계산이 이루어진 후, 그 때까지 선택한 이음선의 집합인 F는 유망하다고 가정한다.
귀납절차 : 집합 F∪{e}가 유망하다는 것을 보여주면 된다. 여기서 e는 가중치가 작은 순서대로 정렬된 이음선이다. 그런데 이음선 e는 E-F에 속한 최소 가중치 이음선 이므로 위의 보조정리에 따라 F∪{e}는 유망하다.