Czy wszystkie drzewa o minimalnej rozpiętości MST są osiągalne przez Kruskala i Prim?

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.

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.$G$

Lemat 1 : Niech i w 2 będą dwiema funkcjami wagi. Poniższe pięć stwierdzeń jest sobie równych.$w_1$$w_2$

1. i w 2 są kompatybilne z porównaniami.$w_1$$w_2$
2. W każdym zestawie krawędzi występuje wspólna najlżejsza krawędź przez i przez w 2 .$w_1$$w_2$
3. W dowolnym zestawie krawędzi występuje najcięższa krawędź przez i przez w 2 .$w_1$$w_2$
4. Istnieje funkcją masy , określające różne wagi do różnych krawędzi tak, że w 3 jest porównanie kompatybilne w 1 i w 2 .$w_3$$w_3$$w_1$$w_2$
5. $e_1$$e_2$$e_1$$e_2$$e_1$$e_2$

Dowód lematu 1 pozostawia się jako łatwe ćwiczenie.

$w_1$$w_2$$e_1\lt_{w_1}e_2$$e_1\lt_{w_2}e_2$

$w_2$$w_1$

$G$

$G$$G$

Kompatybilny algorytm MST może znaleźć wszystkie MST.

$m$$G$$w_1$$m$$w_2$$e_1$$e_2$$w_1$$e_1$$e_2$$w_2$$w_1$$w_2$$m$$w_2$$w_2$$m$$w_1$$w_2$$m$$w_2$$m$$w_1$

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.

• algorytm usuwania ciężkich krawędzi. Zacznij od wszystkich krawędzi. Kilkakrotnie znajdź cykl i usuń jedną z jego najcięższych krawędzi, aż nie pozostanie żaden cykl.
• algorytm dodawania nie-ciężki. Zacznij od pustego zestawu. Iteruj przez wszystkie krawędzie. Każda krawędź jest dodawana, a jeśli powstaje cykl, usuń jedną z najcięższych krawędzi.
• $T$$T$$e$$T$$t$$e$$t$$T$$e$$T$$T$

Poniższy algorytm MST nie jest kompatybilny z porównaniem.

• $S$$\{ab,bc,cd\}$$a,b,c$$ab$$1$$bc, cd, db$$2$

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?

$G$

• $F$$G$$F$
• $S$
• $S$$F$
  • $S$
  • $S$
  • $F$
• $F$

$w_1$$w_2$$G$$S$$w_1$$w_2$

Algorytm jest kompatybilny z porównaniem, jeśli, luźno mówiąc, można go opisać w trzech etapach.

1. rób coś, co nie wiąże się z wagą.
2. wybierz krawędź o minimalnej wadze w danym zestawie krawędzi
3. wybierz krawędź o maksymalnej wadze w danym zestawie krawędzi

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