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). A legrövidebb út feladat, konzervatív súlyfüggvény fogalma. A Bellman-Ford algoritmus.
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ü5ggő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.
Konzervatív súlyfüggvények irányított gráfokban
Konzervatív súlyfüggvény
A $G = (V, E)$ irányított gráf élein a $w : E \to \mathbb{R}$ súlyfüggvényt **konzervatívnak** nevezzük, ha $G$ minden irányított körének éleire a $w(e)$ értékek összege nemnegatív.
A konzervatív súlyfüggvények alapvető jelentőséggel bírnak a hálózati optimalizálásban. Egy ilyen hálózatban garantált, hogy nem találunk olyan "végtelen ciklust", amely mentén haladva az összköltség (vagy súly) folyamatosan csökkenne, így a legrövidebb utak keresése stabil és értelmezhető feladat marad.
Utak és élsorozatok konzervatív súlyozás mellett
Legyen adott a $G = (V,E)$ irányított gráf, az $s,v \in V(G), s \neq v$ csúcsok és $G$ élein a $w : E \to \mathbb{R}$ konzervatív súlyfüggvény. Ekkor, ha létezik $s$-ből $v$-be egy $t$ összsúlyú, $k$ élből álló $Q$ élsorozat, akkor létezik $s$-ből $v$-be egy legföljebb $t$ összsúlyú és legföljebb $k$ élű $P$ út is.
Ha $Q$ eleve irányított út, akkor az állítás magától értetődően igaz. Ha nem, akkor létezik olyan csúcs, amit $Q$ egynél többször érint.
Keressünk $Q$-ban egy olyan ismétlődő csúcspárt, amik között $Q$ mentén haladva az élek számában mért távolság a lehető legkisebb; jelölje ezt a csúcsot $u$ és $Q$-nak az $u$ legközelebbi elfordulásai közötti szakaszát $C$.
Ekkor $C$ persze egy $u$-ból $u$-ba vezető zárt élsorozat, de ennél több is igaz rá: irányított kör kell legyen. Valóban, ha nem az volna, akkor létezne olyan $w$ csúcs, amit $C$ belül ismételne, ami ellentmondana $C$ (és $u$) választott minimális távolságának.
Mivel a súlyfüggvény **konzervatív**, a $C$ irányított kör összsúlya $w(C) \ge 0$. Ha $Q$-ból elhagyjuk a $C$ szakaszt, egy új $Q'$ élsorozatot kapunk $s$ és $v$ között, amire:
- Az élek száma csökkent ($k' < k$).
- Az összsúly nem nőtt ($t' = t - w(C) \le t$).
Ezt az eljárást véges sokszor megismételve (amíg minden kört el nem távolítunk), végül egy $s \to v$ irányított utat kapunk, amely teljesíti a feltételeket.
A bizonyítás logikája: Shortcut-elv
A bizonyítás lényege, hogy a körök "felesleges" plusz élek. Ha a kör súlya nemnegatív, akkor az elhagyásával csak javíthatunk (vagy szinten tarthatunk) az összsúlyon, miközben egyszerűsítjük az utat.
Legrövidebb utak optimalitási részfeltétele
Legyen adott a $G = (V,E)$ irányított gráf, az $s,v \in V(G)$ csúcsok és $G$ élein a $w : E \to \mathbb{R}$ konzervatív súlyfüggvény. Ha az $s$-ből $v$-be vezető $P$ legrövidebb út áthalad az $u$ csúcson, akkor $P$-nek az $s$-től $u$-ig tartó $P_u$ szakasza egy $s$-ből $u$-ba vezető legrövidebb út.
Tegyük fel indirekt, hogy létezik $s$-ből $u$-ba egy $P_u$-nál rövidebb $P'$ út.
Ekkor $s$-ből $P'$ mentén $u$-ig haladva, majd onnan $P$-nek az $u$-tól $v$-ig tartó szakaszán tovább folytatva egy $s$-ből $v$-be vezető $Q$ élsorozatot kapunk. Fontos megjegyezni, hogy $Q$ nem feltétlen út, mert $P'$-nek lehet közös éle vagy csúcsa $P$ $u$-tól $v$-ig tartó szakaszával.
Mivel $P_u$-t a nála rövidebb $P'$-vel helyettesítettük, ezért $Q$ összsúlya kisebb $P$-énél. Így a korábbi állításunk (10.8) értelmében létezik a gráfban egy $Q$ összsúlyánál nem hosszabb, vagyis $P$-nél rövidebb út is $s$-ből $v$-be.
Ez ellentmond annak a feltevésnek, hogy $P$ a legrövidebb út $s$-ből $v$-be, így az állítást beláttuk.
Ez az összefüggés a dinamikus programozás elvének egyik klasszikus példája: az optimális megoldás részmegoldásai maguk is optimálisak. Ezen alapul többek között a Dijkstra-algoritmus helyessége is.
Rekurzió legrövidebb utakra
Legyen adott a $G = (V,E)$ irányított gráf, az $s,v \in V(G), v \neq s$ csúcsok és $G$ élein a $w : E \to \mathbb{R}$ konzervatív súlyfüggvény. Ekkor minden $k \ge 1$ esetén:
ahol $t_k(v)$ az $s$-ből $v$-be vezető, legföljebb $k$ élből álló élsorozatok közül a legrövidebbnek a hosszát jelöli.
Jelölje $t_k'(v)$ az $s$-ből $v$-be vezető, legföljebb $k$ élből álló legrövidebb élsorozat hosszát. Osztályozzuk ezeket az élsorozatokat az utolsó élük szerint: minden $e = (u,v)$ élre legyen $S_e$ azon élsorozatok halmaza, amelyeknek utolsó éle $e$.
Ha egy $Q \in S_e$ élsorozat a legrövidebbek egyike, akkor az $s$-től $u$-ig tartó $Q'$ szakasza szükségképpen egy $s$-ből $u$-ba vezető, legföljebb $k-1$ élű legrövidebb élsorozat. Ennek hossza definíció szerint $t_{k-1}'(u)$.
Ebből következik, hogy az $S_e$-beli legföljebb $k$ élű élsorozatok közül a legrövidebb hossza pontosan $t_{k-1}'(u) + w(e)$. Mivel minden $s \to v$ élsorozat (ami legalább 1 élű) beletartozik valamelyik $S_e$ halmazba, a globális minimumot ezen értékek minimuma adja meg.
Mivel a súlyfüggvény konzervatív, a legrövidebb élsorozat hossza megegyezik a legrövidebb út hosszával ($t_k(v) = t_k'(v)$), így az állítási beli rekurzió helyes.
A Bellman-Ford algoritmus
Az algoritmus leírása
Bemenet: Egy $n$ csúcsú $G = (V, E)$ irányított gráf, egy $w : E \to \mathbb{R}$ súlyfüggvény és egy $s \in V$ kezdőpont.
Az algoritmus lényege, hogy legfeljebb $n-1$ élből álló utakat vizsgálunk, mivel konzervatív súlyozás mellett a legrövidebb út nem tartalmazhat kört. A $t_k(v)$ érték a $k$. iteráció után az $s$-ből $v$-be vezető, legfeljebb $k$ élű utak minimális összsúlyát tárolja.
Bellman-Ford algoritmus a gyakorlatban
11.5. Feladat
Határozzuk meg a Bellman-Ford algoritmussal a 11.1. ábrán látható gráfban az $x = -1$ választással minden $v$ csúcsra az $s$-ből $v$-be vezető legrövidebb út $táv(v)$ hosszát, és adjunk meg egy $s$-ből $d$-be vezető legrövidebb utat.
| $k$ | $v \mapsto táv_k(v)$ | $v \mapsto előző_k(v)$ | |||||||
|---|---|---|---|---|---|---|---|---|---|
| $s$ | $a$ | $b$ | $c$ | $d$ | $a$ | $b$ | $c$ | $d$ | |
| 0 | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $*$ | $*$ | $*$ | $*$ |
| 1 | 0 | 6 | $\infty$ | 5 | $\infty$ | $s$ | $*$ | $s$ | $*$ |
| 2 | 0 | 6 | 8 | 4 | 4 | $s$ | $c$ | $a$ | $c$ |
| 3 | 0 | 6 | 7 | 4 | 3 | $s$ | $c$ | $a$ | $c$ |
| 4 | 0 | 6 | 7 | 4 | 2 | $s$ | $c$ | $a$ | $b$ |
A táblázat utolsó sorában látható $táv_4(v)$, illetve $előző_4(v)$ értékek az eljárás 15. sora szerint egyenlők a kimenetet alkotó $táv(v)$, illetve $előző(v)$ értékekkel.
Eredmény: Út-visszakövetés
Az $előző(v)$ mutatók mentén $d$-ből visszafelé haladva az alábbi láncot kapjuk:
A legrövidebb út tehát: $s \to a \to c \to b \to d$, hossza pedig $táv(d) = 2$.
Negatív körök detektálása
Konzervatív súlyozás feltétele
Legyen adott a Bellman-Ford algoritmus egy bemenete ($G, w, s$). Jelölje $G_s$ azt a gráfot, amit $G$-ből kapunk az $s$-ből irányított úton nem elérhető csúcsok és az $s$-be belépő élek törlésével.
Módosítsuk az algoritmust: a ciklus fusson $k = 1$-től $n$-ig. Ekkor $w$ akkor és csak akkor **konzervatív** $G_s$-en, ha minden $v \neq s$ csúcsra:
($\Rightarrow$) irány: Ha $w$ konzervatív $G_s$-en, akkor a 10.8. állítás miatt a legrövidebb élsorozatok hossza megegyezik a legrövidebb utakéval. Mivel egy út legfeljebb $n-1$ élet tartalmazhat, a $t_{n-1}(v)$ értékek már az optimális távolságokat adják, így a $k=n$. lépésben már nem történhet javítás.
($\Leftarrow$) irány: Tegyük fel indirekt, hogy $w$ nem konzervatív, azaz létezik egy negatív összsúlyú $C$ kör. Ekkor $C$ csúcsaiba tetszőlegesen kis összsúlyú élsorozatot készíthetünk: $s$-ből elmegyünk a körig, majd sokszor körbejárunk.
Ha az algoritmust tetszőlegesen sokáig futtatnánk, a $t_k(v)$ értékek sosem stabilizálódnának, hanem a negatív kör miatt tartanának $-\infty$-be. Ha bármely $k$-ra beállna az egyenlőség minden csúcsra, az értékek a továbbiakban sem változhatnának, ami ellentmondana annak, hogy a súlyok alulról nem korlátosak a negatív kör mentén.
Ö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 Konzervatív súlyozás
Mikor mondjuk egy súlyfüggvényre, hogy konzervatív irányított gráfban?
#04 Bellman-Ford leállás
Hogyan detektálja az algoritmus a negatív összsúlyú köröket az n-edik lépésben?
Tudtad-e?
A "Dinamikus Programozás" titka
A Bellman-Ford algoritmus alapját adó dinamikus programozás elnevezése Richard Bellman politikai trükkje volt. Olyan nevet keresett, amivel elrejtheti kutatása matematikai jellegét a technológiát ellenző felettesei elől; a "dinamikus" szó jól hangzott, a "programozás" pedig akkoriban tervezést jelentett.
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.
Pénzügyi arbitrázs
A Bellman-Ford algoritmus negatív köröket detektáló képességét a devizapiacokon is használják. Ha a valutaváltási árfolyamok gráfjában negatív kör jelenik meg, az egy arbitrázs lehetőség: a pénz folyamatos körbeváltásával elméletileg végtelen profit termelhető.
Természeti optimumok
A legrövidebb utak optimalitási elve a természetben is megjelenik. A fény is mindig a leggyorsabb utat választja (Fermat-elv), és a hangyák is feromoncsíkok segítségével találják meg a legrövidebb útvonalat az élelemforrás és a boly között.