Algoritmus obráceného mazání - Reverse-delete algorithm

Graf a strom
vyhledávací algoritmy
Výpisy
související témata

The algoritmus zpětného mazání je algoritmus v teorie grafů slouží k získání a minimální kostra od daného připojeného, hranově vážený graf. Poprvé se objevil v Kruskal (1956), ale nemělo by být zaměňováno s Kruskalův algoritmus který se objevuje ve stejném papíru. Pokud je graf odpojen, najde tento algoritmus minimální kostru pro každou odpojenou část grafu. Sada těchto minimálních spanningových stromů se nazývá minimální spanning forest, který obsahuje každý vrchol v grafu.

Tento algoritmus je a chamtivý algoritmus, výběr nejlepší volby v každé situaci. Je to naopak Kruskalův algoritmus, což je další chamtivý algoritmus k nalezení minimálního kostry. Kruskalův algoritmus začíná prázdným grafem a přidává hrany, zatímco algoritmus obráceného mazání začíná původním grafem a odstraňuje z něj hrany. Algoritmus funguje následovně:

  • Začněte grafem G, který obsahuje seznam hran E.
  • Projděte E v sestupném pořadí hmotností hran.
  • U každé hrany zkontrolujte, zda odstraněním hrany se graf dále odpojí.
  • Proveďte jakékoli odstranění, které nevede k dalšímu odpojení.

Pseudo kód

funkce ReverseDelete (hrany [] E) je    třídit E v sestupném pořadí Definujte index i ← 0    zatímco i < velikost(E) dělat        Definovat okraj ← E[i]	    vymazat E[i]	    -li graf není připojen pak                E[i] ← okraj                i ← i + 1    vrátit se hrany [] E

Ve výše uvedeném grafu je sada hran E přičemž každá hrana obsahuje závaží a spojené vrcholy v1 a v2.

Příklad

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

Zpětné mazání 0.svgToto je náš původní graf. Čísla poblíž okrajů označují jejich hmotnost hran.
Zpětné mazání 1. svgAlgoritmus bude začínat maximální váženou hranou, která v tomto případě je DE s hmotností hrany 15. Jelikož odstranění hrany DE dále neodpojuje graf, je odstraněno.
Zpětné mazání 2. svgDalší největší hrana je FG takže algoritmus zkontroluje, zda odstranění této hrany dále odpojí graf. Vzhledem k tomu, že odstranění hrany nebude dále odpojovat graf, bude hrana poté odstraněna.
Zpětné mazání 3. svgDalší největší hrana je hrana BD takže algoritmus tuto hranu zkontroluje a hranu odstraní.
Zpětné mazání 4. svgDalší hrana ke kontrole je hrana NAPŘ, který nebude smazán, protože by odpojil uzel G z grafu. Další hrana, kterou chcete odstranit, je tedy hrana před naším letopočtem.
Zpětné mazání 5.svgDalší největší hrana je hrana EF takže algoritmus tuto hranu zkontroluje a hranu odstraní.
Zpětné odstranění 6.svgAlgoritmus poté prohledá zbývající hrany a nenajde další hranu k odstranění; proto se jedná o konečný graf vrácený algoritmem.

Provozní doba

Je možné ukázat, že algoritmus běží Ó(E log PROTI (log log PROTI)3) čas (pomocí big-O notace ), kde E je počet hran a PROTI je počet vrcholů. Této vazby je dosaženo takto:

  • Třídění hran podle hmotnosti pomocí srovnávacího řazení trvá Ó(E log E) čas, který lze zjednodušit na Ó(E log PROTI) s využitím skutečnosti, že největší E může být je PROTI2.
  • Existují E iterace smyčky.
  • Odstranění okraje, kontrola konektivity výsledného grafu a (pokud je odpojeno) opětovné vložení okraje lze provést v Ó(logPROTI (log log PROTI)3) čas na operaci (Thorup 2000 ).

Důkaz správnosti

Doporučuje se přečíst si doklad o Kruskalův algoritmus za prvé.

Důkaz se skládá ze dvou částí. Nejprve je dokázáno, že hrany, které zůstanou po aplikaci algoritmu, tvoří překlenovací strom. Zadruhé je prokázáno, že kostra má minimální váhu.

Překlenující strom

Zbývající dílčí graf (g) vytvořený algoritmem není odpojen, protože algoritmus to zkontroluje v řádku 7. Výsledný dílčí graf nemůže obsahovat cyklus, protože pokud ano, pak při pohybu podél hran narazíme na maximální hranu v cyklu a tuto hranu odstraníme. Tedy g musí být kostra hlavního grafu G.

Minimalita

Ukážeme, že následující návrh P je pravda indukcí: Pokud F je množina okrajů, které zůstaly na konci smyčky while, pak existuje nějaký minimální kostra, která (její hrany) jsou podmnožinou F.

  1. Jasně P drží před začátkem smyčky while. protože vážený připojený graf má vždy minimální rozpínací strom a protože F obsahuje všechny okraje grafu, musí být tento minimální rozpínací strom podmnožinou F.
  2. Nyní předpokládejme P platí pro nějakou sadu koncových hran F a nechte T být 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á i jiný) spanning tree T ', který je podmnožinou F.
    1. pokud další odstraněná hrana e nepatří k T, pak T = T 'je podmnožinou F a P drží. .
    2. jinak, pokud e patří do T: nejprve si všimněte, že algoritmus odstraní pouze okraje, které nezpůsobí odpojení v F. takže e nezpůsobí odpojení. Ale odstranění e způsobí odpojení ve stromu T (protože je členem T). Předpokládejme, že e odděluje T do dílčích grafů t1 a t2. Jelikož je celý graf připojen po odstranění e, pak musí existovat cesta mezi t1 a t2 (jiná než e), takže musí existovat cyklus C v F (před odstraněním e). nyní musíme mít v tomto cyklu další hranu (nazvěme ji f), která není v T, ale je v F (protože pokud by všechny hrany cyklu byly ve stromu T, už by to nebyl 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 odstraněním hrany ve stromu a přidáním další hrany, která nezpůsobí cyklus, získáme další strom se stejnými vrcholy. protože T byl klenutý strom, tak T 'musí být kostra také. protože přidání „f“ nezpůsobí žádné cykly, protože „e“ je odstraněno. (Všimněte si, že strom T obsahuje všechny vrcholy grafu).
    4. za druhé dokážeme, že T 'je minimální kostra. máme tři případy pro hrany „e“ a „f“. wt je váhová funkce.
      1. wt (f)
      2. wt (f)> wt (e) to je také nemožné. od té doby, když procházíme hranami v sestupném pořadí hmotností hran, musíme nejprve vidět „f“. protože máme cyklus C, takže odstranění „f“ by nezpůsobilo odpojení v F. takže by jej algoritmus odstranil z F dříve. takže „f“ neexistuje v F, což je nemožné (prokázali jsme, že f existuje v kroku 4.
      3. takže wt (f) = wt (e), takže T 'je také a minimální kostra. tak znovu P drží.
  3. tak P drží, když je smyčka while hotová (což je, když jsme viděli všechny hrany) a na konci jsme dokázali, že F se stane a kostra a víme, že F má minimální překlenující strom jako jeho podmnožinu. takže F musí být minimální kostra sám.

Viz také

Reference

  • Kleinberg, Jon; Tardos, Éva (2006), Návrh algoritmu, New York: Pearson Education, Inc..
  • Kruskal, Joseph B. (1956), „Na nejkratším podstromu grafu a problému obchodního cestujícího“, Proceedings of the American Mathematical Society, 7 (1): 48–50, doi:10.2307/2033241, JSTOR  2033241.
  • Thorup, Mikkel (2000), „Téměř optimální plně dynamické připojení grafu“, Proc. 32. ACM Symposium on Theory of Computing, str. 343–350, doi:10.1145/335305.335345.