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

13

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.

domoremath
źródło
2
Odpowiednia odpowiedź i dyskusja na inny wynik, który możesz wykorzystać jako lemme.
Raphael
3
Pierwsza część mojej odpowiedzi potwierdza to dla algorytmu Kruskala i myślę, że podobny argument działałby dla
Prim'a

Odpowiedzi:

9

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.w1w2

  1. i w 2 są kompatybilne z porównaniami.w1w2
  2. W każdym zestawie krawędzi występuje wspólna najlżejsza krawędź przez i przez w 2 .w1w2
  3. W dowolnym zestawie krawędzi występuje najcięższa krawędź przez i przez w 2 .w1w2
  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 .w3w3w1w2
  5. e1e2e1e2e1e2

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

w1w2e1<w1e2e1<w2e2

w2w1

G

GG

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

mGw1mw2e1e2w1e1e2w2w1w2mw2w2mw1w2mw2mw1

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.
  • TTeTtetTeTT

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

  • S{ab,bc,cd}a,b,cab1bc,cd,db2

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

  • FGF
  • S
  • SF
    • S
    • S
    • F
  • F

w1w2GSw1w2

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

John L.
źródło