Uważam, że to prawda, ale nie udało mi się uzyskać formalnego dowodu. Ale czy to prawda, że każde minimalne drzewo opinające jest osiągalne dzięki zastosowaniu algorytmu Kruskala? Podobnie, czy dotyczy to algorytmu Prim?
EDYCJA: Aby być bardziej precyzyjnym, chcę wiedzieć, czy otrzymując MST dla połączonego, niekierowanego, ważonego wykresu, czy jest zagwarantowane, że istnieje sekwencja kroków przy użyciu Kruskala lub Prim, które generują ten MST. Np. Kruskal ma różne możliwości wyboru, jeśli istnieje wiele krawędzi o tej samej masie. Podobnie dla Prim.
algorithms
graphs
minimum-spanning-tree
domoremath
źródło
źródło
Odpowiedzi:
Jak wskazuje komentarzu Rafaela i komentarzu j_random_hacker za odpowiedź jest pozytywna. W rzeczywistości każdy MST jest osiągalny przez dowolny algorytm MST z pewnymi drobnymi wyjątkami.
W przypadku wykresu dwie funkcje wagowe na wszystkich krawędziach (do liczb rzeczywistych) są zdefiniowane jako (słabo) kompatybilne z porównaniem (względem siebie), jeśli możemy rozszerzyć ścisłe słabe uporządkowanie na krawędziach wywołane przez każdą funkcję wagi do tego samego ścisłego całkowite zamówienie. Oznacza to, że możemy opracować spójne reguły zerwania wiązania dla każdej funkcji wagi, tak aby wynik porównania dowolnych dwóch krawędzi według jednej funkcji wagi i jej reguł zrywania wiązań był taki sam, jak wynik dla drugiej funkcji wagi i jej wiązania łamanie zasad.sol
Dowód lematu 1 pozostawia się jako łatwe ćwiczenie.
Kompatybilny algorytm MST może znaleźć wszystkie MST.
Każdy algorytm MST jest kompatybilny z porównaniami
Powyższa propozycja brzmi zbyt daleko. Cóż, przez każdy algorytm MST rozumiem każdy ogólny algorytm MST oparty na porównaniu, który widziałem, z wyjątkiem tych pozornie patologicznych, takich jak błędne lub niepotrzebne kroki. Ponieważ algorytm MST zgodny z porównaniem może znaleźć wszystkie MST, każdy algorytm MST może znaleźć wszystkie MST. W szczególności każdy z czterech klasycznych algorytmów MST , mianowicie algorytmy Borůvka, Prim's, Kruskal i odwrotnego usuwania mogą znaleźć wszystkie MST.
Oto trzy kolejne kompatybilne algorytmy MST.
Poniższy algorytm MST nie jest kompatybilny z porównaniem.
Należy pamiętać, że wszystkie osiem wyżej wymienionych algorytmów MST jest opartych na porównaniu.
Jak pokazać algorytm kompatybilny z porównaniami?
Algorytm jest kompatybilny z porównaniem, jeśli, luźno mówiąc, można go opisać w trzech etapach.
Ten wystarczający warunek obejmuje algorytm Borůvka, Prim's, Kruskal, algorytm odwrotnego usuwania, usuwania z grubą krawędzią i dodawania nie grubszego. Zauważ, że aby spełnić ten wystarczający warunek, możemy zmienić niektóre opisy algorytmu bez wpływu na zestaw osiągalnych MST. Z powodu wyjątku zgodnego z porównaniem algorytmu Kruskala z tendencją do stopniowania, podkreślam, że ten wystarczający warunek jest opisany luźno
źródło