Minimális feszítőfák bevezetés (Spanning tree algorithms)

Célunk az, hogy találjunk az éleknek egy olyan részhalmazát, amely körmentes és amelynek segítségével az összes pont összekapcsolható, és a teljes súlya a lehető legkisebb. A körmentes és minden csúcspontot összekapcsoló élek részhalmaza egy fa, amelyik kifeszíti a gráfot, ezért feszítőfának nevezzük.

Összefüggő, irányítatlan, élsúlyozott gráf minimális feszítőfáját keressük. Tehát a cél, hogy találjunk a lehető legkisebb összsúllyal rendelkező feszítőfák közül egyet, amellyel tetszőleges csúcsból bármelyik másikba el lehet jutni. Lehet több minimális feszítőfája is egy gráfnak, ha vannak azonos élsúlyú élek.

Alapfogalmak:

Feszítő erdő:

A $G = (V, E)$ irányítatlan gráf feszítő erdeje a $T = (V, F)$ gráf, ha $F \subseteq E$ és $T$ olyan irányítatlan gráf, aminek mindegyik komponense irányítatlan fa, a fák páronként diszjunktak, és együtt éppen lefedik a $G$ csúcshalmazát.

Feszítőfa:

A $G = (V, E)$ irányítatlan, összefüggő gráf feszítőfája a $T = (V, F)$ gráf, ha $F \subseteq E$, és $T$ fa.

Minimális feszítőfa:

A $G$ irányítatlan, összefüggő, élsúlyozott gráf minimális feszítőfája $T$, ha $T$ feszítőfája $G$-nek és bármely másik feszítőfára igaz, hogy az élek összsúlya nagyobb vagy egyenlő, mint $T$ összsúlya.

Biztonságos él:

Biztonságos az él, ha ezzel bővítve egy $A$ élhalmazt, $G$ összefüggő, irányítatlan, élsúlyozott gráf valamelyik minimális feszítőfája élhalmazának a részhalmaza marad $A$. ( $A \subseteq G$ ).

Vágás:

Ha $G = (V, E)$ gráf és $\{\} \subsetneq S \subsetneq V$ , akkor a $G$ gráfon $(S, V \setminus S)$ egy vágás.

Keresztező él:

A $G = (V, E)$ gráfon az $(u, v) \in E$ él keresztezi az $(S, V \setminus S)$ vágást, ha $(u \in S \land v \in V \setminus S) \lor (u \in V \setminus S \land v \in S)$.

Könnyű él a vágásban:

Az $(u, v) \in E$ könnyű él az $(S, V \setminus S)$ vágásban, ha $(u, v)$ keresztezi a vágást, és $\forall (p, q)$ vágást keresztező élre igaz, hogy $w(u, v) \leq w(p, q)$.

Élhalmazt elkerüli a vágás:

A $G = (V, E)$ gráfban az $A \subseteq E$ élhalmazt elkerüli az $(S, V \setminus S)$ vágás, ha az $A$ egyetlen éle sem keresztezi a vágást.

Tétel:

Ha a $G = (V, E)$ irányítatlan, összefüggő, élsúlyozott gráfon

• $A$ részhalmaza a $G$ valamelyik minimális feszítőfája élhalmazának,
• az $(S, V \setminus S)$ vágás elkerüli az $A$ élhalmazt,
• az $(u, v) \in E$ könnyű él az $(S, V \setminus S)$ vágásban,

akkor az $(u, v)$ él biztonságosan hozzávehető az $A$ élhalmazhoz.

Általános minimális feszítőfa algoritmus:

Az algoritmus az éleknek, azt az $A$-val jelölt halmazát kezeli, amelyre az alábbi invariáns állítás teljesül:

• Az iterációk előtt az $A$ valamelyik minimális feszítőfának a részhalmaza.

Az algoritmus minden lépésben, azt az $(u, v)$ élt határozza meg, amelyiket az $A$-hoz téve, továbbra is fennáll az előbbi invariáns állítás, miszerint $A \cup {(u, v)}$ is egy részhalmaza az egyik minimális feszítőfának. Egy ilyen élt $A$-ra nézve biztonságos élnek hívunk, mivel $A$-hoz történő hozzávétele biztosan nem rontja el az $A$-ra vonatkozó invariáns állítást. Egy kezdetben üres $A$ élhalmazt újabb és újabb biztonságos éllel bővítünk, akkor $|G.V |−1$ bővítés után éppen a $G$ egyik minimális feszítőfáját kapjuk meg.

$GenMST(G : \mathcal{G}_{w} ; \space A : \mathcal{E}\{\})$

---

$A := \{\}$
$k := |G.V| - 1$
	$k > 0$
	$find \space an \space edge \space (u, v) \space that \space is \space safe \space for \space A$
	$A := A \cup \{(u, v)\}$
	$k-−$