[일반] 크루스칼 알고리즘이 항상 MST를 구할수잇음을 어떻게증명함??

[익명(129.130)]

크루스칼 알고리즘 써서 만든 트리 T가 최소가 아니라고 가정했을때 가중치에 보여지는 모순을 이용해야하나? 하아

[유사수학자(lonelymath)]

알고리즘이 진행되면서 간선 하나씩 추가할텐데, 예를 들어서 i번째로 추가된 간선을 e_i라 하고 중간 결과물을 T_i라 할때, 어떤 MST T*가 존재해서 T*가 T_i를 포함함을 증명하면 됨.

[익명(129.130)]

[유사수학자(lonelymath)]

그래프 위의 간선집합 위에서 정의된 가중치함수를 w라 하겠음. 그리고 < 를 간선들을 가중치 순서대로 정렬한 순서라고 하겠음. 두 간선 e,f에 대해서 e < f라는건 이 순서에서 e가 f보다 앞에 있다는 뜻.

[유사수학자(lonelymath)]

수학적 귀납법을 이용해서 증명함. 먼저 아무 간선을 포함하지 않는 T_0은 임의의 MST가 포함하므로 성립하고, 만약 T_{i-1}를 포함하는 MST가 존재하는데 T_i를 포함하는 MST가 존재하지 않는다고 가정하면, T_{i-1}을 포함하는 MST를 T*라 할때 T* + e_i를 생각하면 스패닝트리에 간선 하나 추가한 그래프니까 e_i를 포함하는 유일한 사이클 C가 존재함.

[유사수학자(lonelymath)]

(1) 만약 C 위의 간선들 중에서 w(e_i) < w(e)를 만족하는 간선 e가 있으면, T' = T* + e_i - e로 두면 T'의 가중치합은 T*의 가중치합에 w(e_i) - w(e)를 더한 값이므로, T*보다 가중치합이 작으므로 T*가 MST임에 모순임. 따라서, C 위의 임의의 간선 e에 대해서 w(e) ≤ w(e_i)를 만족함.

[유사수학자(lonelymath)]

(2) 따라서 만약 e_i < e인 간선 e가 C 위에 있다면, w(e_i) ≤ w(e)이므로 (1)의 결론으로부터 w(e) = w(e_i)를 만족해야함. 마찬가지로 T' = T* + e_i - e로 두면, T'는 e_i를 포함하는 스패닝트리이고 e_i < e이므로 e는 T_{i-1} 바깥에 있으므로, T'는 T_i를 포함하는 스패닝트리임. 하지만 w(e_i) = w(e)이므로 T*와 T'의 가중치합은 같으므로 T' 또한 MST이므로, T_i를 포함하는 MST가 존재하지 않는다는 가정에 모순.

[유사수학자(lonelymath)]

(3) 따라서 C 위의 임의의 간선 e ≠ e_i에 대해서 w(e) ≤ w(e_i)와 e < e_i를 만족함. 하지만 이것은 C - e_i의 모든 간선이 < 의 순서에서 e_i 이전에 나왔다는 뜻인데, (C - e_i의 모든 간선) ∪ T_{i-1}의 모든 간선은 T*의 간선집합의 부분집합이니 사이클을 포함하지 않으므로 사이클을 만들어내지 않으면 < 의 순서대로 간선을 무조건 추가하는 크루스칼 알고리즘으로부터 C - e_i는 T_{i-1}에 포함되어야 함. 근데 이건 사이클 C 전체가 T_i에 포함된다는걸 의미하기 때문에 모순 (알고리즘에서 T_{i-1}에 e_i를 추가했을때 사이클이 생기면 e_i를 추가하지 않아야 하니까).

[익명(129.130)]

오 트루매스매티션센세 진쟈감사합니다 차근차근읽어보면서 정리해보겟음 ㄳㄳ

[익명(49.170)]

그래픽 매트로이드

[익명(49.170)]

아니넹

[익명(121.166)]

Sedgewick의 Algorithms Ch4에 상세한 증명이 나와있던걸로 기억함

[익명(121.166)]

글고 보통 저런 유명한건 kruskal algorithm proof 이런식으로 구글에 검색하면 다 나옴