2 Souvislost grafů Pokud máme graf, který modeluje nějaká spojení či síť, přirozeně nás zajímá, jakou máme možnost se dostat odněkud někam v tomto grafu. To má množství praktických motivací -například počítačové, dopravní, telefonní či potrubní sítě. Je pochopitelné, že v takových sítích chceme mít možnost se dostat z každého místa do každého jiného. Grafům s takovou vlastností říkáme souvislé. Stručný přehled lekce • Definice souvislosti grafu, vrcholová / hranová, vyšší souvislost. • Algoritmus procházení grafem (souvislou komponentou). • Eulerovské grafy. Petr Hliněný, Fl MU Bn MA010: Souvislost grafu 2.1 Spojení vrcholů, komponenty Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran vo,ei,vi,e2,v2, .. .,en,vn. ve které vždy hrana ej má koncové vrcholy ví-i,ví. Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). c Lema 2.1. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy u ~ v právě když existuje v G sled začínající vu a končící ve v. Pak ~ je relací ekvivalence. Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou sledem délky 0. Symetrická je také, protože sled z u do v snadno obrátíme na sled z » do ti. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. - D Definice: Třídy ekvivalence výše popsané (Lema 2.1) relace ~ na V(G) se nazývají komponenty souvislosti grafu G. Jinak se taky komponentami souvislosti myslí pod grafy indukované na těchto třídách ekvivalence. Petr Hliněný, Fl MU Brno 2 Fl: MA010: Souvislost grafu r Připomeňme si, že cesta v grafu je vlastně sledem bez opakovaní vrcholu. Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta, c Důkaz. Nechť u = vo, ei, v\,..., en, vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled T^ z vrcholu wo = w, který už bude cestou: - Předpokládejme, že nový sled W už má počátek wo, ei, »i,..., Wj (na začátku « = 0, tj. jen wo bez hran), kde wí = Vj pro některé j G {0,1,..., n}, a - Najdeme největší index k > j takový, že vj. = Vj = Wi, a sled W pokračujeme krokem ...,Wi=Vj= vk, ek+1, wi+1 = vk+1,.... d - Zbývá dokázat, že nový vrchol Wj+i = vk+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo wi = Wj+i, / < i, pak bychom na vrchol Wj+i „přeskočili" už dříve z vrcholu wi, spor. - Nakonec skončíme, když Wi = v. D Ačkoliv uvedený důkaz vypadá složitě, je to jen jeho formálním zápisem. Ve skutečnosti se v důkaze neděje nic jiného, než že se původní sled zkracuje o opakované vrcholy, až nakonec zákonitě vznikne cesta. Jeho výhodou je konstruktivnost - vidíme, jak cestu získat. ________str Hliněný, Fl MU Brn< .010: Souvislost grafu Důkaz kratší, ale nekonstruktivní, pro Větu 2.2: Ze všech sledů mezi vrcholy u a v v G vybereme sled W s nejmenší délkou. Je snadno vidět, že pokud W zopakuje některý vrchol grafu G, můžeme W ještě zkrátit, a to je spor s předpokladem. Proto je W cestou v G. D Závěrem se dostáváme k nejdůležitější definici souvislého grafu: Definice 2.3. Graf G je souvislý pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou (dle Věty 2.2). Podívejte se, kolik komponent souvislosti má tento graf: Vidíte obě dvě komponenty? Petr Hliněný, Fl MU Bn MA010: Souvislost grafu Pro vytvoření co nejobecnějšího schématu algoritmu pro procházení grafu vystačíme s následujícími datovými stavy a pomocnou strukturou: • Vrchol: má stavy ... - iniciační - dostane na začátku, - nalezený- poté, co jsme jej přes některou hranu nalezli, - zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející. • Hrana: má stavy ... - iniciační - dostane na začátku, - zpracovaná - poté, co už byla probrána od jednoho ze svých vrcholů, c • Úschovna: je pomocná datová struktura (množina), - udržuje nalezené a ještě nezpracované vrcholy. Poznámka: Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu. V prohledávaných vrcholech a hranách se pak provádějí konkrétní programové akce pro prohledání a zpracování našeho grafu. ________str Hliněný, Fl MU Brn< .010: Souvislost grafu Algoritmus 2.4. Procházení souvislé komponenty grafu Algoritmus projde a zpracuje každou hranu a vrchol souvislého grafu G. vstup < graf G; stav (všechny vrcholy a hrany G) = iniciační; úschovna U = {libovolný vrchol vq grafu G}; stavOo) = nalezený; while (Uje neprázdná) { vybrat v G U; U = U\{v}; ZPRACUJ(v); foreach (e hrana vycházející z v) { if (stav(e)==iniciační) ZPRACUJ(e); w = opačný vrchol hrany e = vw; if (stav(w)==iniciační) { stav(w) = nalezený; U = UU{w}; } stav(e) = zpracovaná; } stav (v) = zpracovaný; } G zpracovaný; Petr Hliněný, Fl MU Brno 6 Fl: MA010: Souvislost grafu Způsoby implementace procházení grafu • Procházení „do hloubky" - úschovna Uje implementovaná jako zásobník, tj. dále prohledáváme od posledních nalezených vrcholů, d • Procházení „do šířky" - úschovna U je implementovaná jako fronta, tj. dále prohledáváme od prvních nalezených vrcholů. • Dijkstrův algoritmus pro nejkratší cestu - z úschovny vybíráme vždy vrchol nejbližší k počátečnímu vq. (Toto je dost podobné prohledávání do šířky, ale obecnější i pro případy, kdy hrany nejsou „stejně dlouhé".) Tento algoritmus bude popsán v příští lekci, d Příklad 2.11. Ukázka průchodu následujícím grafem do hloubky z vrcholu a. /* = --* e "-A 9 *c---------------i 3 '\ --p-—\ >d -* c a®- Y Detr Hliněný, Fl MU Bn MA010: Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•;; — •_ C Detr Hliněný, Fl MU Bn MA010: Souvislost grafu Příklad 2.12. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -•' 3 ~~~> d f j ~~-> d ff t=:-------1 •? ~~~-? d Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu příkladu? Ü V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním „vyšších" stupňů souvislosti grafu, c Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných nejvýše k — 1 hran z G zůstane výsledný graf souvislý, c Definice: Graf G je vrcholově k-souvislý, k > 1, pokud i po odebrání libovolných nejvýše k — 1 vrcholů z G zůstane výsledný graf souvislý. Speciálně úplný graf Kn je vrcholově (n — l)-souvislý Pokud mluvíme jen o fc-souvislém grafu, máme na mysli vrcholově fc-souvislý graf. Stručně řečeno, vysoká hranová souvislost znamená vysoký stupeň odolnosti sítě proti výpadkům spojení-hran, neboli síť zůstane stále dosažitelná, i když libovolných k — 1 spojení bude přerušeno. Vysoká vrcholová souvislost je mnohem silnějším pojmem, znamená totiž, že síť zůstane dosažitelná i po výpadku libovolných k — \ uzlů-vrcholů (samozřejmě mimo těch vypadlých uzlů). 'etr Hliněný, Fl MU Brno 10 Fl: MA010: Souvislost grafu Na ilustračním obrázku má první graf vrcholovou souvislost 4 a snadno vidíme, že po odebrání tří vrcholů či hran zůstává souvislý. Z druhého grafu bychom museli odebrat nejméně 3 hrany, aby se stal nesouvislým, a proto je jeho hranová souvislost 3. Na druhou stranu však stačí odebrat 2 vrcholy, aby mezi jeho levým a pravým krajním vrcholem žádné spojení nezůstalo. (Vidíte, které dva?) A jak je tomu u třetího grafu?c Věta 2.5. Libovolný obyčejný graf je 2-souvislý právě když jej lze vytvořit z kružnice „přidáváním uší"; tj. iterací operace, kdy libovolné dva stávající vrcholy grafu jsou spojeny novou cestou libovolné délky (ale ne paralelní hranou). etr Hliněný, Fl MU Bn MA010: Souvislost grafu Důkaz následujícího důležitého výsledku by nebyl jednoduchý při použití stávajících znalostí, proto jej ponecháme na pozdější lekce.. . („Toky v sítích".) Věta 2.6. Graf G je hranově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k hranově-disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k disjunktních cest (různých až na ty dva spojované vrcholy). Věta nám vlastně říká, že stupeň souvislosti grafu se přirozeně rovná stupni redundance spojení vrcholů. Na výše uvedeném obrázku mezi každými dvěma vrcholy prvního grafu můžeme vést až 4 disjunktní cesty. U druhého grafu třeba mezi levým a pravým koncem lze vést jen 2 (vrcholově) disjunktní cesty, ale mezi každými dvěma vrcholy lze vést 3 hranově-disjunktní cesty. etr Hliněný, Fl MU Brno 12 Fl: MA010: Souvislost grafu V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky. Věta 2.7. Nechť G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici. Důkaz: Nechť e,f£ E(G). Sestrojíme graf G' podrozdělením obou hran e, / novými vrcholy ve,Vf. Je zřejmé, že i G' je vrcholově 2-souvislý graf, takže podle Věty 2.6 existují v G' dvě disjunktní cesty spojující ve s Vf, tvořící spolu kružnici C'. Nakonec C indukuje v G kružnici C procházející e i /. ü Rozšířením předchozí úvahy lze dokonce dokázat: Věta 2.8. Nechť G je vrcholově k-souvislý graf k > 1. Pak pro každé dvě disjunktní množiny Ui, U i C V (G), \Ui\ = \U2\ = k v G existuje k po dvou disjunktních cest z vrcholů U\ do vrcholů U2- Ui -* -• Uo 3etr Hliněný, Fl MU Bn MA010: Souvislost grafu 2.4 Jedním tahem: Eulerovské grafy Snad nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera -jedná se o slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningradě. kjsisovtmci :riE: 0 jaký problém se tehdy jednalo? Městští radní chtěli vědět, zda mohou suchou nohou přejít po každém ze sedmi vyznačených mostů právě jednou. 3etr Hliněný, Fl MU Bn \/IA010: Souvislost grafu Rozbor tohoto problému vede k následující definici a odpovědi. Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Otevřený tah je tahem, který končí v jiném vrcholu, než ve kterém začal. Nejstarší výsledek teorie grafů od Leonarda Eulera poté zní: c Věta 2.9. Graf G lze nakreslit jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně. Důsledek 2.10. Graf G lze nakreslit jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně. 3etr Hliněný, Fl MU Bn MA010: Souvislost grafu Důkaz: Dokazujeme oba směry ekvivalence. Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. □ Naopak zvolíme mezi všemi uzavřenými tahy T v G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' = G — E (T), o kterém předpokládejme, že je neprázdný. Jelikož G' má taktéž všechny stupně sudé, je (z indukčního předpokladu) libovolná jeho komponenta C C G' nakreslená jedním uzavřeným tahem Tc- - Vzhledem k souvislosti grafu G každá komponenta C C G' protíná náš tah T v některém vrchole w, a tudíž lze oba tahy Tc a T „propojit přes w". To je spor s naším předpokladem nejdelšího možného T. D Důkaz důsledku: Nechť u,v jsou dva vrcholy grafu G mající lichý stupeň, neboli dva (předpokládané) konce otevřeného tahu pro G. Do G nyní přidáme nový vrchol w spojený hranami s u a v. Tím jsme náš případ převedli na předchozí případ grafu se všemi sudými stupni. D etr Hliněný, Fl MU Brno 16 Fl: MA010: Souvislost grafu