Algorytm Kruskala MST z Find And Union

Question

Algorytm Kruskala do szukania MST jest prosty. Sortujemy krawędzie po wagach, jeżeli są w różnej spójnej, to łączymy, w jakiej spójnej sprawdzamy Union Findem.

Wszystko by było spoko, tylko niezbyt rozumiem dlaczego to zawsze jest optymalne, w sensie dlaczego nie opłaca nam się użyć krawedzi o większej wadze.

Bardzo proszę o wytłumaczenie.

Z góry dzięki!

Answer 1

Tu jest prosty dowód przez indukcję. Idea jest taka, że gdyby krawędź (powiedzmy e) dodana przez algorytm Kruskala nie należała do MST to stworzyłaby w tym MST cykl. Ale przez to w jaki sposób algorytm Kruskala wybiera te krawędzie (czyli od najmniejszej do największej wagi) możemy dowieść, że na tym cyklu istnieje inna krawędź o tej samej wadze co e. Wystarczy zatem usunąć tamtą krawędź z MST i dodać e i ostatecznie suma wag w MST się nie zmieni.