10. Összefüggőség
10. Többszörös összefüggőség és élösszefüggőség, illetve κ(G) és λ(G) fogalma, Menger ezekre vonatkozó tételei (a pontösszefüggőség és κ(G) esetében bizonyítás nélkül). Minimális összsúlyú feszítőfa, Kruskal algoritmusa.
k-szoros összefüggőség
k-szoros összefüggőség
Legyen $G$ (irányítatlan) gráf és $k \ge 1$ tetszőleges egész.
-
A $G$ gráfot **$k$-szorosan él összefüggőnek** mondjuk, ha az élei közül bárhogyan legfeljebb $(k-1)$-et törölve mindig összefüggő gráfot kapunk.
-
$G$-t **$k$-szorosan pont összefüggőnek** (vagy röviden $k$-szorosan összefüggőnek) mondjuk, ha legalább $k+1$ csúcsa van és a csúcsai közül bárhogyan legfeljebb $(k-1)$-et (az azokra illeszkedő élekkel együtt) törölve mindig összefüggő gráfot kapunk.
Ezek a fogalmak a hálózatok hibatűrését számszerűsítik. Míg az egyszerű összefüggőség csak egyetlen út létezését garantálja, a $k$-szoros összefüggőség biztosítja, hogy a gráf szerkezete több elem kiesése után is stabil maradjon.
Él- és pont-összefüggőségi szám
Összefüggőségi számok
A $G$ gráfra $\lambda(G)$, illetve $\kappa(G)$ jelöli a legnagyobb olyan $k$ egészet, amire $G$ $k$-szorosan él-összefüggő, illetve $k$-szorosan pont-összefüggő.
Gyakorlati szempontból $\lambda(G)$ és $\kappa(G)$ a hálózat „töréspontjait” mutatja meg. A $\lambda(G)$ érték azt adja meg, hány élt kell minimálisan eltávolítani a gráf széteséséhez, míg $\kappa(G)$ ugyanezt a csúcsokra vonatkoztatja. Általánosságban elmondható, hogy egy hálózat akkor igazán stabil, ha mindkét érték magas.
Menger tétele többszörös összefüggőségre
Legyen $G$ (irányítatlan) gráf és $k \ge 1$ egész szám. Ekkor:
- (i) $G$ akkor és csak akkor **$k$-szorosan él-összefüggő**, ha bármely két különböző csúcsa között létezik $k$ éldiszjunkt út.
- (ii) $G$ akkor és csak akkor **$k$-szorosan pont-összefüggő**, ha legalább $k+1$ csúcsú és bármely két különböző csúcsa között létezik $k$ pontdiszjunkt út.
Bizonyítás az élváltozatra (i)
Elegendőség ($\Leftarrow$): Tegyük fel, hogy $G$ bármely két különböző csúcsa között létezik $k$ éldiszjunkt út. Hagyjunk el $G$-ből tetszőlegesen legföljebb $k-1$ élet, a kapott gráfot jelölje $G'$. Ekkor bármely $s, t \in V(G), s \neq t$ csúcsok között léteznie kell útnak $G'$-ben, hiszen a $G$-ben köztük lévő $P_1, \dots, P_k$ éldiszjunkt utak közül legalább egy $G'$-ben is érintetlenül megmarad. Mivel egy él elhagyása legföljebb egy utat tehet tönkre, és mi $k$-nál kevesebb élt töröltünk, a gráf összefüggő marad.
Szükségesség ($\Rightarrow$): Tegyük fel, hogy $G$ $k$-szorosan él-összefüggő. Ha egy $s$ és $t$ csúcspár között nem létezne $k$ éldiszjunkt út, akkor az élváltozatú Menger-tétel szerint létezne egy legföljebb $k-1$ elemű lefogó élhalmaz. Ennek eltávolítása után a gráf szétesne, ami ellentmondana a $k$-szoros él-összefüggőség feltételének.
Kidolgozott feladat: Összefüggőségi számok meghatározása
10.14. Feladat
A $G$ gráf csúcshalmaza legyen $V(G) = \{10, 11, 12, \dots, 39\}$ és két csúcs akkor legyen szomszédos $G$-ben, ha a megfelelő számok első számjegye különböző. Határozzuk meg $\lambda(G)$ és $\kappa(G)$ értékét!
Megoldás
Vezessük be a $V_1 = \{10, \dots, 19\}$, $V_2 = \{20, \dots, 29\}$ és $V_3 = \{30, \dots, 39\}$ jelöléseket. Ekkor két csúcs pontosan akkor szomszédos $G$-ben, ha $V_1, V_2$ és $V_3$ közül nem ugyanabba esnek. (Ez egy teljes 3-partit gráf, ahol minden osztály 10 elemű.)
A pont-összefüggőség ($\kappa(G)$) vizsgálata
$G$-ből el lehet hagyni 20 csúcsot úgy, hogy a kapott gráf ne legyen összefüggő: például $V_1 \cup V_2$ elhagyásával csak a $V_3$ csúcsaiból álló, él nélküli gráf marad. Így $G$ nem 21-szeresen összefüggő. Ha viszont legfeljebb 19 tetszőleges csúcsot hagyunk el, a gráf összefüggő marad, hiszen bármely két megmaradt csúcs vagy szomszédos, vagy van közös szomszédjuk. Ezért $\kappa(G) = 20$.
Az él-összefüggőség ($\lambda(G)$) vizsgálata
$G$-ben minden pont foka 20, hiszen minden $v \in V_i$ csúcs a $V_i$-n kívüli 20 csúccsal szomszédos. Ezért 20 él elhagyásával (egy csúcs összes élével) az összefüggőség megszüntethető, tehát $\lambda(G) \le 20$. A részletesebb elemzés megmutatja, hogy legfeljebb 19 él elhagyása után bármely két csúcs között marad út (akár 1, 2 vagy 3 hosszú). Így $\lambda(G) = 20$.
Az összefüggőségi számok kapcsolata
Ha a $G$ gráf $k$-szorosan pont-összefüggő, akkor $k$-szorosan él-összefüggő is.
Tegyük fel, hogy $G$ $k$-szorosan pont-összefüggő. Menger tételének (ii) állítása szerint ekkor a gráf bármely két csúcsa között létezik $k$ pontdiszjunkt út.
Mivel a pontdiszjunkt utak egyben éldiszjunktak is, ezért bármely két csúcs között létezik $k$ éldiszjunkt út is.
Ebből Menger tételének (i) állítása szerint valóban következik, hogy $G$ $k$-szorosan él-összefüggő.
Ez a következmény formálisan is alátámasztja azt az intuitív tényt, hogy a pontok elhagyása „pusztítóbb” a gráfra nézve, mint az éleké. Ebből adódik az összefüggőségi számok közötti alapvető egyenlőtlenség: $\kappa(G) \le \lambda(G)$.
Összefüggőség vizsgálata Hamilton-körrel
10.17. Feladat
Legyen $H$ a 10.1. ábrán látható gráfból az élek irányításának figyelmen kívül hagyásával kapott gráf. Mutassuk meg, hogy $\lambda(H) = 3$ és $\kappa(H) = 2$.
10.4. Ábra: H élei Hamilton-körrel (kék) és feszítőfával (piros)
Megoldás
Korábban láttuk, hogy $H$ nem négyszeresen él-összefüggő és nem háromszorosan pont-összefüggő, mert az $\{ \{p,q\}, \{p,v\}, \{y,z\} \}$ élhalmaz, illetve a $\{p,z\}$ csúcshalmaz elhagyásával kapott gráfok nem összefüggőek.
A 10.4. ábrán $H$ éleit két színnel jelöltük: a kék élek egy $C$ **Hamilton-kört**, a pirosak pedig egy $F$ **feszítőfát** alkotnak $H$-ban.
Így $\lambda(H) = 3$ és $\kappa(H) = 2$ teljesül.
Minimális feszítőfa és a mohó algoritmus
Ha a $G$ összefüggő gráf $F_{mohó}$ feszítőfáját úgy készítjük el, hogy az üres halmaztól indulva mindig az aktuális részgráf különböző komponenseit összekötő, **legkisebb súlyú** élek egyikével bővítjük az élhalmazt, akkor $F_{mohó}$ **minimális összsúlyú** feszítőfa $G$-ben.
Bizonyítás (Indirekt módon)
Számozzuk meg $G$ éleit $e_1, e_2, \dots, e_m$ sorrendben a súlyuk szerint: $w(e_1) \leq w(e_2) \leq \dots \leq w(e_m)$.
Vizsgáljuk meg az első eltérést az $e_k = \{u,v\}$ élnél:
-
1
$e_k \notin F_{mohó}$ de $e_k \in F_{opt}$: Ez csak akkor történhetett, ha a mohó algoritmus azért utasította el $e_k$-t, mert az a korábban beválasztott (és $F_{opt}$-tal közös) élekkel **kört alkotott** volna. Ez ellentmond $F_{opt}$ körmentességének.
-
2
$e_k \in F_{mohó}$ de $e_k \notin F_{opt}$: Mivel $F_{opt}$ feszítőfa, létezik benne egy $u-v$ út. Ebben kell lennie egy $e_\ell$ élnek, ami nincs benne $F_{mohó}$-ban. $e_k$ bevétele és $e_\ell$ kivétele egy új, optimális feszítőfát ad, ami több élben egyezik a mohóval — ez ellentmondás.
A Mohó Stratégia Működése
Az algoritmus "vak" bizalma a legolcsóbb élben kifizetődő: a lokális döntések sorozata garantáltan a globális minimumhoz vezet.
Kruskal algoritmusa
Bemenet: Egy $n$ csúcsú és $m$ élű $G = (V,E)$ összefüggő gráf és egy $w: E \to \mathbb{R}$ súlyfüggvény.
RENDEZZÜK AZ ÉLEKET a $w(e)$ súlyok szerinti növekvő sorrendbe: $w(e_1) \leq w(e_2) \leq \dots \leq w(e_m)$
$k \leftarrow 0$; $j \leftarrow 1$; $E(F) \leftarrow \emptyset$
ciklus: amíg $k < n - 1$
VIZSGÁLJUK MEG, HOGY $e_j$ VÉGPONTJAI KÜLÖNBÖZŐ KOMPONENSBEN VANNAK-E
ha igen, akkor:
$E(F) \leftarrow E(F) \cup \{e_j\}$ // Él beválogatása
$k \leftarrow k + 1$
$j \leftarrow j + 1$
ciklus vége
Leállási feltétel
Az algoritmus pontosan $n-1$ él beválogatása után áll meg. Mivel egy $n$ csúcsú fa élszáma mindig ennyi (lásd a korábbi **2.3-as tételt**), ekkorra garantáltan egy összefüggő feszítőfát kapunk.
Komponens vizsgálat
A 4. lépés a „lelke” a körmentességnek: ha két pont már azonos komponensben van, egy új él kört zárna be közöttük. Ezt elkerülve az algoritmus végig erdő struktúrát tart fenn.
Kruskal-algoritmus: Interaktív szimuláció
Gráfépítő vászon
Kattints a vászonra csúcsokhoz, kösd össze őket az élekért!
Algoritmus lépései
Összefoglaló Kvíz
Gráf-összefüggőség és Algoritmusok
Vidd az egeret a kártyák fölé az ellenőrzéshez!
#01 Pont-összefüggőség feltétele
Miben tér el a $k$-szoros pont-összefüggőség definíciója az él-összefüggőségétől a csúcsok számát tekintve?
#02 Összefüggőségi hierarchia
Melyik összefüggőségi szám nem lehet soha nagyobb a másiknál?
#03 Mohó stratégia Kruskalban
Milyen feltétel alapján dönti el a Kruskal-algoritmus, hogy beválogat-e egy élet az MST-be?
#04 Kruskal leállása
Hány él beválogatása után állhat le garantáltan a Kruskal-algoritmus egy $n$ csúcsú gráfban?
Tudtad-e?
Villamoshálózatok és MST
A minimális feszítőfa problémáját (MST) legelőször Otakar Borůvka cseh matematikus írta le 1926-ban. Célja nem tisztán elméleti volt: Morvaország elektromos hálózatának legolcsóbb kiépítési tervét próbálta megalkotni.
Hálózati robusztusság
Az összefüggőségi szám ($\kappa$) közvetlenül méri egy hálózat hibatűrését. A modern internethálózatokat és az űreszközök belső rendszereit úgy tervezik, hogy magas legyen ez az érték, így több kritikus csomópont egyidejű meghibásodása esetén is megmarad a kapcsolat.
Joseph Kruskal és a Mohó elv
Joseph Kruskal 1956-ban publikálta algoritmusát. Zsenialitása abban rejlik, hogy egy "mohó" (greedy) stratégiát alkalmaz: mindig a pillanatnyilag legolcsóbb élt választja, és matematikailag bizonyítható, hogy ez a lokálisan legjobb döntés a végén a globálisan legolcsóbb hálózathoz vezet.
Természeti optimumok
A legrövidebb utak és minimális hálózatok optimalitási elve a természetben is megjelenik. A nyálkagombák például képesek a táplálékforrások között olyan hálózatot kiépíteni, amely kísértetiesen hasonlít egy minimális feszítőfára, sőt, le is utánozzák vele a tokiói vasúthálózatot!