Algoritmus zpětného mazání

Algoritmus zpětného mazání  je algoritmus v teorii grafů , který se používá k získání minimálního kostry z daného připojeného grafu váženého čarami . Algoritmus se poprvé objevil v Kruskalově článku [1] , ale neměl by být zaměňován s Kruskalovým algoritmem , který se objevil ve stejném článku. Pokud graf není propojen, tento algoritmus najde minimální kostru pro každou jednotlivou část grafu. Množina těchto minimálních překlenovacích stromů se nazývá minimální překlenovací les, který obsahuje všechny vrcholy grafu.

Algoritmus je chamtivý algoritmus poskytující nejlepší řešení. Je opakem Kruskalova algoritmu , což je další chamtivý algoritmus minimálního spanning tree. Kruskalův algoritmus začíná z prázdného grafu a přidává hrany, zatímco algoritmus zpětného mazání začíná z původního grafu a odstraňuje z něj hrany. Algoritmus funguje takto:

Pseudokód

1 funkce ReverseDelete(hrany[] E ) 2 seřaďte E v sestupném pořadí 3 Určete index i ← 0 4 zatímco i < velikost ( E ) 5 Definujte hranu ← E [ i ] 6 odstranit E [ i ] 7 , pokud graf není připojen 8 E [ i ] ← hrana 9 i ← i + 1 10 vratných hran[] E

Příklad

V následujícím příkladu jsou zelené okraje prohledány algoritmem a červené okraje jsou algoritmem odstraněny.

Toto je původní graf. Čísla vedle hran odrážejí váhu hran.
Algoritmus začíná hranou s maximální váhou, v tomto případě hranou DE s váhou 15. Protože odstranění hrany DE nevede k rozpojenému grafu, hrana se odstraní.
Další nejtěžší hrana je FG , takže algoritmus zkontroluje, zda by odstranění hrany vedlo k odpojení. Protože odstranění hrany nezpůsobí odpojení grafu, hrana se odstraní.
Další nejtěžší hrana je BD , takže algoritmus kontroluje, zda odstranění hrany způsobí její odpojení a odstraní hranu.
Další hranou ke kontrole je EG , kterou nelze odstranit, protože to povede k oddělení vrcholu G od grafu. Další hranou k odstranění je tedy BC .
Další nejtěžší hrana je EF , takže algoritmus tuto hranu zkontroluje a odstraní.
Algoritmus prohlédne zbývající hrany a nenajde žádnou vhodnou k odstranění, takže toto je konečný graf, který algoritmus vrátí.

Otevírací doba

Lze ukázat, že algoritmus běží v čase ( "O" je velké a "o" je malé ), kde E  je počet hran a V  je počet vrcholů. Tohoto limitu je dosaženo následovně:

Důkaz správnosti

Doporučuje se nejprve přečíst důkaz Kruskalova algoritmu .

Důkaz se skládá ze dvou částí. Nejprve je dokázáno, že hrany, které zůstanou po spuštění algoritmu, mají podobu kostry. Pak se prokáže, že tento kostrč má optimální hmotnost.

Spanning tree

Zbývající podgraf (g) získaný algoritmem je připojen, protože algoritmus to kontroluje na řádku 7. Podgraf nemůže obsahovat cyklus, protože jinak pohybem po cyklu můžete najít hranu s největší váhou a odstranit ji. Potom g musí být kostra hlavního grafu G.

Minimalita

Indukcí ukážeme, že platí následující tvrzení P : Jestliže F je množina hran zbývajících na konci cyklu, pak existuje nějaká minimální kostra, která (jeho hrany) je podmnožinou F .

  1. Je jasné, že P se provede před začátkem cyklu while . Protože vážený souvislý graf má vždy minimální kostru a protože F obsahuje všechny hrany grafu, musí být tato minimální kostra podmnožinou F.
  2. Nyní předpokládejme, že P platí pro nějakou mezilehlou množinu hran F a nechť T je minimální kostra, která je obsažena v F . Musíme ukázat, že po odstranění hrany e v algoritmu existuje nějaká (možná jiná) kostra T', která je podmnožinou F .
    1. jestliže další odstraněná hrana e nepatří do T, pak T=T' je podmnožinou F a P je splněno.
    2. v opačném případě, pokud hrana e patří k T: nejprve si všimněte, že algoritmus odstraňuje pouze hrany, F.zničenínezpůsobíkteré Předpokládejme, že e rozloží T na podgrafy t1 a t2. Protože celý graf zůstane po odstranění e propojený, musí existovat cesta mezi t1 a t2 (jiná než e ), takže v F musí existovat cyklus C (před odstraněním e ). Nyní musíme mít v tomto cyklu další hranu (ať je to f), která nepatří do T, ale je v F (protože kdyby všechny hrany cyklu byly ve stromu T, nebyl by to strom). Nyní tvrdíme, že T' = T - e + f je minimální kostra, která je podmnožinou F.
    3. Nejprve dokážeme, že T' je kostra . Víme, že smazáním hrany ve stromu a přidáním další hrany nevznikne cyklus a získáme další strom se stejnými vrcholy. Protože T byla kostra, T' musí být také kostra . Potom přidání "f" nevytvoří žádný cyklus, protože "e" je odstraněno (všimněte si, že strom T obsahuje všechny vrcholy grafu).
    4. Potom dokážeme, že T' je minimální kostra. Máme tři případy pro hrany "e" a "f" definované váhovou funkcí wt.
      1. Případ wt(f) < wt(e), což je nemožné, protože to znamená, že váha T' je striktně menší než T. Protože T je minimální kostra, to prostě není možné.
      2. Případ je wt(f) > wt(e), což je nemožné, protože když projíždíme hrany v sestupném pořadí vah, měli bychom nejprve vidět "f". Protože máme C, odstranění "f" nevede k odpojení v F, takže algoritmus by musel odstranit hranu z F dříve. To znamená, že "f" nepatří do F, což je nemožné (v kroku 4 jsme dokázali, že f ano).
      3. Případ wt(f) = wt(e), takže T' je minimální kostra, takže P je opět splněno.
  3. P se tedy provede poté, co smyčka skončí (tj. poté, co byly prohlédnuty všechny hrany) a dokázali jsme, že na konci se F stane kostrou a víme, že F má minimální kostru jako podmnožinu, takže F sama musí být minimální kostra .

Viz také

Poznámky

  1. ↑ Kruskal, 1956 .
  2. ↑ Thorup, 2000 .

Odkazy