Minimální strom překlenutí překážek - Minimum bottleneck spanning tree

V matematice, a minimální překlenovací strom (MBST) v neorientovaném grafu je a kostra ve kterém je nejdražší hrana co nejlevnější. Hrana úzkého hrdla je nejvyšší vážená hrana v kostře. Spanning tree je minimální spanning tree, pokud graf neobsahuje spanning tree s menší váhou hrany úzkého hrdla.^[1] U směrovaného grafu je podobný problém známý jako Minimální zúžení rozpětí Arborescence (MBSA).

Definice

Neorientované grafy

Minimální překlenutí překlenující strom

{ displaystyle G (V, E)}

V neorientovaném grafu $G (PROTI, E)$ a funkce $w : E \to R$ , nechť $S$ být sadou všech klenutých stromů T_i. Nechat B(T_i) být hranou maximální hmotnosti pro jakýkoli kostru T_i. Definujeme podmnožinu minimálních překážek překlenujících stromy STakové, že pro každého $T j \in S'$ a $T k \in S$ my máme $B (T j) \leq B (T k)$ pro všechny i ak.^[2]

Graf vpravo je příkladem MBST, červené okraje v grafu tvoří MBST $G (PROTI, E)$ .

Směrované grafy

Minimální zúžení rozpětí Arborescence G (V, E)

Arborescence grafu G je směrovaný strom G který obsahuje směrovanou cestu ze zadaného uzlu L ke každému uzlu podmnožiny PROTI′ Z $PROTI \{L}$ . Uzel L se nazývá kořen arborescence. Arborescence je klenutá arborescence, pokud $PROTI′ = PROTI \{L}$ . MBST je v tomto případě spanning arborescence s minimálním zúženým okrajem. MBST se v tomto případě nazývá Minimum Bottleneck Spanning Arborescence (MBSA).

Graf vpravo je příkladem MBSA, červené okraje v grafu tvoří MBSA $G (PROTI, E)$ .

Vlastnosti

MST (nebo minimální kostra ) je nutně MBST, ale MBST nemusí být nutně MST.^[3]

^[4]

Cameriniho algoritmus pro neorientované grafy

Navrhla Camerini^[5] an algoritmus slouží k získání minimálního úzkého místa překlenujícího stromu (MBST) v daném neřízeném, připojeném, hranově vážený graf v roce 1978. Napůl rozděluje hrany na dvě sady. Váhy hran v jedné sadě nejsou větší než v druhé. Pokud kostra existuje v podgrafu složeném pouze s hranami v sadě menších hran, pak vypočítá MBST v podgrafu, MBST podgrafu je přesně MBST původního grafu. Pokud kostra neexistuje, kombinuje každou odpojenou komponentu do nového supervertexu, poté vypočítá MBST v grafu tvořeném těmito super vrcholy a hranami v sadě větších hran. Les v každé odpojené komponentě je součástí MBST v původním grafu. Tento postup opakujte, dokud v grafu nezůstanou dva (super) vrcholy a nebude přidán jeden okraj s nejmenší váhou. Je nalezen MBST skládající se ze všech hran nalezených v předchozích krocích.^[4]

Pseudo kód

Procedura má dva vstupní parametry. G je graf, w je pole vah všech hran v grafu G.^[6]

 1  funkce MBST (graf G, závaží w) 2  E ← sada okrajů G  3  -li | E | = 1 pak vrátit se E jiný 4      A ← poloviční hrany dovnitř E jejichž hmotnosti nejsou menší než střední hmotnost 5 B ← E - A 6      F ← les G_B 7      -li F je klenutý strom pak 8          vrátit se MBST (G_B,w) 9      jiný 10         vrátit se MBST ((G_A)_η, w)  ${ displaystyle cup}$  F

Ve výše uvedeném (G_A)_η je podgraf složený ze super vrcholů (pozorováním vrcholů v odpojené komponentě jako jednoho) a hran v A.

Provozní doba

Algoritmus běží Ó (E) čas, kde E je počet hran. Této vazby je dosaženo takto:

dělení do dvou sad s algoritmy pro nalezení mediánu v Ó(E)
najít les v Ó(E)
s ohledem na poloviční okraje v E v každé iteraci Ó(E + E/2 + E/4 + ··· + 1) = Ó(E)

Příklad

V následujícím příkladu se zelené hrany používají k vytvoření MBST a přerušované červené oblasti označují super vrcholy vytvořené během kroků algoritmu.

	Algoritmus napůl rozděluje hrany na dvě sady s ohledem na váhy. Zelené hrany jsou hrany, jejichž váhy jsou co nejmenší.
	Vzhledem k tomu, že v podgrafu je klenutý strom tvořený pouze hranami v sadě menších hran. Vyhledání MBST v tomto podgrafu opakujte.
	Vzhledem k tomu, že v aktuálním podgrafu není překlenující strom vytvořený s hranami v aktuální sadě menších hran. Zkombinujte vrcholy odpojené komponenty se super vrcholem (označeným čárkovanou červenou oblastí) a pak najděte MBST v podgrafu vytvořeném se super vrcholy a hranami ve větších sadách hran. Les vytvořený v rámci každé odpojené komponenty bude součástí MBST v původním grafu.
	Opakujte podobné kroky kombinací více vrcholů do super vrcholu.
	Algoritmus nakonec získá MBST pomocí hran nalezených během algoritmu.

Algoritmy MBSA pro směrované grafy

Pro směrovaný graf jsou k dispozici dva algoritmy: Cameriniho algoritmus pro hledání MBSA a další od Gabow a Tarjana.^[4]

Cameriniho algoritmus pro MBSA

U směrovaného grafu se Cameriniho algoritmus zaměřuje na nalezení sady hran, které by měly své maximální náklady jako úzké místo MBSA. To se provádí rozdělením sady okrajů E do dvou sad A a B a údržbu sady T to je množina, ve které je známo, že G_T nemá překlenující stromovost, roste T podle B kdykoli maximální stromovost G(B ∪ T) není překlenující arborescence G, jinak klesáme E podleA. Celková časová složitost je Ó(E logE).^[5]^[4]

Pseudo kód

funkce MBSA (G, w, T) je    E ← sada okrajů G     -li | E - T | > 1 pak        A ← UH (E-T) B ← (E - T) − A        F ← BUSH (G_ALE)        -li F je klenutá arborescence G pak            S ← F MBSA (((G_ALE), w, T)        jiný            MBSA (G, w, VANA);

T představuje podmnožinu E, u které je známo, že G_T neobsahuje žádnou spanning arborescence zakořeněnou v uzlu „a“. Zpočátku je T prázdný
UH vezme (E − T) sadu hran v G a vrátí A ⊂ (E − T) tak, že:
1. ${ displaystyle | A | = left lfloor { frac {(| E-T |)} {2}} right rfloor}$
2. Ž_A ≥ W_b , pro a and A a b ∈ B
BUSH (G) vrací maximální arborescenci G zakořeněnou v uzlu „a“
Konečným výsledkem bude S.

Příklad

	Po spuštění první iterace tohoto algoritmu dostaneme $F$ a $F$ není překlenující arborescence $G$ , Takže spustíme kód ${ displaystyle MBSA (G, w, T cup B).}$
	Ve druhé iteraci dostaneme ${ displaystyle F '}$ a ${ displaystyle F '}$ také není překlenující arborescence $G$ , Takže spustíme kód ${ displaystyle MBSA (G, w, T ' cup B')}$
	Ve třetí iteraci dostaneme ${ displaystyle F ''}$ a ${ displaystyle F ''}$ je překlenující se stromovitost $G$ , Takže spustíme kód ${ displaystyle MBSA (G_ {T '' cup B ''}, w, T '')}}$
	když spustíme ${ displaystyle MBSA (G_ {T '' cup B ''}, w, T '')}}$ , ${ displaystyle \| E-T \|}$ je rovno 1, což není větší než 1, takže se algoritmus vrátí a konečný výsledek je ${ displaystyle S = F ''}$ .

Algoritmus Gabow a Tarjan pro MBSA

Gabow a Tarjan poskytli úpravu Dijkstrův algoritmus pro nejkratší cestu s jedním zdrojem, která produkuje MBSA. Jejich algoritmus běží Ó(E + PROTI logPROTI) čas, pokud Fibonacciho hromada použitý.^[7]

Pseudo kód

 Pro graf G (V, E), F je sbírka vrcholů v PROTI. Zpočátku, F = {s} kde s je výchozí bod grafu G a C(s) = -∞ 1  funkce MBSA-GT (G, w, T) 2      opakovat | V | krát 3 Vyberte proti s minimem C(proti) z F; 4 Smažte jej z F; 5          pro ∀ hrana (v, w) dělat 6              -li w ∉ F nebo ∉ Strom pak 7 přidat w na F;           8                  C(w) = C(v, w); 9                  p(w) = proti;      10             jiný 11                 -li w ∈ F a c (w)> c (v, w) pak 12                     C(w) = C(v, w); 13                     p(w) = proti;

Příklad

Následující příklad ukazuje, jak algoritmus funguje.

V prvním kroku algoritmu vybereme kořen s z grafu G, na výše uvedeném obrázku je vrchol 6 kořen s. Pak jsme našli celou hranu (6, w) ∈ E a jejich cenu c (6, w), kde w ∈ V.

Dále se přesuneme na vrchol 5 v grafu G, našli jsme všechny hrany (5, w) ∈ E a jejich cenu c (5, w), kde w ∈ V.

Dále se přesuneme na vrchol 4 v grafu G, našli jsme všechny hrany (4, w) ∈ E a jejich cenu c (4, w), kde w ∈ V. Zjistili jsme, že hrana (4,5)> hrana (6,5), takže ponecháme hranu (6,5) a hranu (4,5) odstraníme.

Dále se přesuneme na vrchol 1 v grafu G, našli jsme všechny hrany (1, w) ∈ E a jejich cenu c (1, w), kde w ∈ V. Zjistili jsme, že hrana (5,2)> hrana (1,2), takže odstraníme hranu (5,2) a ponecháme hranu (1,2).

Dále se přesuneme na vrchol 2 v grafu G, našli jsme všechny hrany (2, w) ∈ E a jejich cenu c (2, w), kde w ∈ V.

Dále se přesuneme na vrchol 3 v grafu G, našli jsme všechny hrany (3, w) ∈ E a jejich cenu c (3, w), kde w ∈ V. Zjistili jsme, že hrana (3,4)> hrana (6,4), takže odstraníme hranu (3,4) a ponecháme hranu (6,4).

Poté, co projdeme všechny vrcholy v grafu G, algoritmus skončil.

Další přístup navržený Tarjanem a Gabowem s vazbou na $Ó (E log * PROTI)$ pro řídké grafy, ve kterých je velmi podobný Cameriniho algoritmu pro MBSA, ale spíše než rozdělení sady hran do dvou sad na každou iteraci, $K. (i)$ byl představen ve kterém i je počet uskutečněných rozdělení nebo jinými slovy číslo iterace a $K. (i)$ je rostoucí funkce, která označuje počet rozdělených sad, které by jedna měla mít na iteraci. $K. (i) = 2 k (i - 1)$ s $k (1) = 2$ . Algoritmus najde $λ *$ ve kterém je to hodnota úzkého okraje v libovolném nástroji MBSA. Po $λ *$ je nalezena jakákoli klenutá arborescence v $G (λ *)$ je MBSA, ve kterém $G (λ *)$ je graf, kde jsou náklady na všechny jeho okraje $\leq λ *$ .^[4]^[7]

Reference

^ Vše o překážkovém stromě Spanning Tree
^ Murali, T. M. (2009), Aplikace minimálních rozpětí stromů (PDF)
^ v otázce 3 máte doklad o tomto nároku (PDF)
^ ^A ^b ^C ^d ^E Traboulsi, Ahmad (2014), Překlenutí překlenující stromy (PDF), archivovány z originál (PDF) dne 04.03.2016, vyvoláno 2014-12-28
^ ^A ^b Camerini, P.M. (1978), "Problém min-max překlenovacího stromu a některá rozšíření", Dopisy o zpracování informací, 7 (1): 10, doi:10.1016/0020-0190(78)90030-3
^ Cui, Yuxiang (2013), Minimální strom překlenutí překážek (PDF), archivovány z originál (PDF) dne 04.03.2016, vyvoláno 2014-12-28
^ ^A ^b Gabow, Harold N; Tarjan, Robert E (1988). "Algoritmy pro dva problémy s optimalizací úzkého místa". Journal of Algorithms. 9 (3): 411–417. doi:10.1016/0196-6774(88)90031-4. ISSN 0196-6774.

[1] Vše o překážkovém stromě Spanning Tree

[2] Murali, T. M. (2009), Aplikace minimálních rozpětí stromů (PDF)

[3] v otázce 3 máte doklad o tomto nároku (PDF)

[Traboulsi2014-4] A ^b ^C ^d ^E Traboulsi, Ahmad (2014), Překlenutí překlenující stromy (PDF), archivovány z originál (PDF) dne 04.03.2016, vyvoláno 2014-12-28

[Camerini1978-5] A ^b Camerini, P.M. (1978), "Problém min-max překlenovacího stromu a některá rozšíření", Dopisy o zpracování informací, 7 (1): 10, doi:10.1016/0020-0190(78)90030-3

[6] Cui, Yuxiang (2013), Minimální strom překlenutí překážek (PDF), archivovány z originál (PDF) dne 04.03.2016, vyvoláno 2014-12-28

[GabowTarjan1988-7] A ^b Gabow, Harold N; Tarjan, Robert E (1988). "Algoritmy pro dva problémy s optimalizací úzkého místa". Journal of Algorithms. 9 (3): 411–417. doi:10.1016/0196-6774(88)90031-4. ISSN 0196-6774.

[1]

[2]

[3]

[4]

[5]

[6]

[7]