[Algorytmy] Więcej niż jedno minimalne drzewo rozpinające

turson · Post autor: **turson** » 20 wrz 2016, o 18:53

Czy w grafie, w którym wszystkie krawędzie mają różne wagi może istnieć więcej niż 1 MST?

Wydaje mi się, że nie co znalazłem na

https://en.wikipedia.org/wiki/Minimum_spanning_tree#Uniqueness

, ale jak to uzasadnić?

Post autor: **Afish** » 20 wrz 2016, o 20:45

W podanym przez Ciebie artykule jest dowód, coś w nim jest niejasne?

turson · Post autor: **turson** » 20 wrz 2016, o 21:17

Zdaje się, że dowód dotyczy "If the edge weights are not unique"

Post autor: **Afish** » 21 wrz 2016, o 06:42

Nie, to jest dowód dla unikalnych wag, z tego założenia korzystamy w punkcie 4.