Ukážeme si pár netriviálních aplikací, ve kterých se nám hodí to, že umíme najít minimální kostru grafu.

Steinerovy stromy

V motivačních problémech na začátku kapitoly o minimálních kostrách jsme si reálnou situaci poněkud zjednodušili. Při elektrifikaci Tibetu jsme zakázali, aby se dráty s elektrickým vedením větvily jinde než ve vesnicích. Pokud to povolíme, tak nám bude k propojení vesnic stačit mnohem méně drátu. Příklad $4$ takových vesnic je na následujícím obrázku.



Jak určit vhodná místa pro větvení elektrického vedení? Zkuste se sami zamyslet nad tím, co taková místa musí splňovat. Kdy je takové místo optimální a kdy je naopak výhodnější ho posunout kousek vedle.

Předpokládejme, že už známe všechna možná místa větvení. V řadě úloh jsou tato místa známa. Například při prohrnování sněhu v reálné silniční síti chceme propojit všechna města. Kromě měst se silnice může větvit i na křižovatkách ležících mimo města. Graf silniční sítě má tedy dva druhy vrcholů, města která chceme vzájemně propojit a křižovatky, které odpovídají místům větvení. V optimálním řešení nám může po propojení všech měst zůstat spousta nedostupných křižovatek (cestu k nim není potřeba prohrnovat). To nás přivádí k následujícímu úkolu.

Úkol (Steinerův strom): Je dán neorientovaný graf $G=(V,E)$ s nezáporným ohodnocením hran $c: E\to \RR_+$. Vrcholy $V=R\cup S$ jsou dvou druhů, požadované $R$ a Steinerovy $S$. Najděte strom $T\subseteq G$ s nejmenší cenou, který propojuje všechny požadované vrcholy. Cena stromu $T$ se opět počítá jako $\sum_{e\in T} c(e)$.

Steinerův strom se od kostry liší tím, že nemusí použít všechny Steinerovy vrcholy. Nalezení optimálního Steinerova stromu patří mezi složité úlohy.1 Není pro ně znám žádný polynomiální algoritmus. Jediné, co umíme v polynomiálním čase spočítat, jsou přibližná řešení (viz. kapitola [ref]aproximacni_algoritmy[/ref] o aproximačních algoritmech).

Aproximační algoritmus pro Steinerův strom

Následujcí aproximační algoritmus funguje pouze v grafech, jejichž ohodnocení hran splňuje trojúhelníkovou nerovnost (pro libovolné $3$ hrany $ab$, $bc$, $ac$ platí $c(ab)+c(bc)\ge c(ac)$).

Aproximační algoritmus:

  1. Graf $G$ obsahuje vrcholy $V=R\cup S$. Vytvoříme si pomocný úplný graf $G’$, který obsahuje pouze požadované vrcholy $R$. Cena hrany $uv\in G’$ je cenou nejkratší cesty z $u$ do $v$ v grafu $G$. Grafu $G’$ se říká metrický uzávěr grafu $G$. Graf $G’$ už je úplným grafem (libovolná dvojice vrcholů určuje hranu). Cena Steinerova stromu v grafu $G’$ je stejná nebo vyšší než cena Steinerova stromu v původním grafu $G$.
  2. Najdeme minimální kostru $T’$ v grafu $G’$. Ta je aproximací Steinerova stromu pro graf $G’$.
  3. Některé hrany $uv$ v kostře $T‘ \subseteq G’$ odpovídají v grafu $G$ cestě spojující vrcholy $u$ a $v$. Proto každou hranu $e\in T’$ nahradíme jí odpovídající cestou. Cesta má stejnou cenu, jako hrana, protože $G’$ je metrickým uzávěrem $G$. Takto ale mohli vzniknout kružnice. Proto výsledný graf projdeme a přebytečné hrany odstraníme (opět nalezneme minimální kostru). Tím ještě snížíme cenu nalezeného řešení. Skončíme s kostrou $T \subseteq G$, která je aproximací Steinerova stromu v $G$.
Lemma: Nechť $OPT$ je cena optimálního Steinerova stromu ${T^*}$ v grafu $G$. Cena stromu $T$ nalezeného algoritmem je $OPT \le c(T)\le 2\cdot OPT$.
Důkaz: Algoritmem nalezený strom $T$ je přípustným řešením úlohy. Proto $OPT \le c(T)$.

Vezmeme optimální Steinerův strom ${T^*}$ v grafu $G$. Zdvojíme hrany stromu ${T^*}$ a nalezneme na nich uzavřený eulerovský tah $W$. Cena $c(W)=2\cdot OPT$.

Každý úsek tahu $W$, který prochází přes Steinerův vrchol $u$ zkrátíme tak, že úsek $v \to u \to w$ procházející přes hrany $vu$, $uw$ nahradíme zkratkou $v \to w$, která prochází pouze přes hranu $vw$. Protože hrany grafu splňují trojúhelníkovou nerovnost, dostaneme levnější tah. Zkracování tahu $W$ budeme aplikovat tak dlouho, dokud nebudou všechny vrcholy tahu $W$ patřit do požadovaných vrcholů $R$.

Potom tah projdeme ještě jednou a pomocí “zkratek” vytvoříme Hamiltonovskou kružnici $H$. Uděláme to tak, že procházíme eulerovský tah. Pokud následující hrana tahu vede do vrcholu, který jsme už navštívili, tak půjdeme zkratkou do prvního z následujících vrcholů tahu, kde jsme ještě nebyli. Cena tahu mohla opět jen klesnout.



Vyhozením nejdražší hrany z kružnice $H$ dostaneme strom $T’^*$. Cena stromu $T’^*$ je $\leq 2\cdot OPT$. Strom $T’^*$ je kostrou v grafu $G’$, ale nemusí být minimální kostrou. Cena minimální kostry je stejná a nebo menší. Protože $T’$ je minimální kostra v $G’$, dostáváme $c(T‘)\le 2\cdot OPT$. Ve 3. kroku algoritmu jsme z kostry $T’\subseteq G’$ vytvořili levnější kostru $T\subseteq G$. Proto je $c(T) \le c(T‘)\le 2\cdot OPT$.