Udowodnij właściwość Minimum Spanning Tree - algorytm, wykres, algorytm kruskalsa, niekierowany-wykres

Potrzebuję twojej pomocy, aby udowodnić, co następuje: G=(V,E) jest nieukierunkowanym połączonym wykresem z nieujemnymi wagami na krawędziach. Pozwolić T bądź MST z G i T" być spanning tree of G (nie minimum), więc to utrzymuje Weight(T") > Weight(T). Udowodnij, że waga najgorszej krawędzi w T" nie jest mniejszy niż ciężar najcięższej krawędzi T.

Nie wiem, jak to zaakceptować, jeśli pozwolimy e(u,v) - heaviest edge on T i e"(u",v") - heaviest edge on T" a następnie, jeśli spojrzymy na cięcie określone przez (u,u") możemy użyć algorytmu Kruskala i to pokazać e" nie został wybrany T czy coś w tym kierunku ...

Dziękuję Ci,

Odpowiedzi:

Załóżmy, że jest inaczej - istnieje ważonyniekierowany wykres z minimalnym drzewem rozpinającym T i rozpinającym się drzewem T „takim, że najcięższa krawędź T jest cięższa niż najcięższa krawędź T”, tj. najcięższa krawędź T jest cięższa niż każdy krawędź w T ”. Zastanów się nad cięciem wywołanym przez usunięcie najcięższej krawędzi h T. Ponieważ T "jest połączone, pewna krawędź w T" przecina to cięcie. Jeśli dodamy tę krawędź do T-h, otrzymamy drzewo rozpinające, które jest lżejsze niż T, które jest minimalnym drzewem rozpinającym. Sprzeczność.

Zmieniłem kierunek. Dla uproszczenia niech wszystkie ciężary krawędzi będą różne, aby MST był wyjątkowy. Rozważ najcięższą krawędź e w MST i sposób, w jaki algorytm Kruskala konstruuje ten MST. Okazuje się, że ostatnia dodana krawędź jest najcięższą krawędzią w wynikowym MST.

Teraz spójrz na sytuację tuż przed dodaniem ostatniej krawędzi. Mamy las składający się z dwóch drzew. Jak idziemy z algorytmem Kruskala, nie ma obecnie tańszych sposobów e połączyć te dwa drzewa. Dlatego każda krawędź między nimi w dowolnym innym opinającym drzewie ma wagę co najmniej tak dużą jak e ma.

Krawędzie o jednakowej wadze wymagają pewnej staranności, a może nawet sprytnego pomysłu, aby były odpowiednio traktowane.