2   Souvislost grafů
Pokud mame graf, který modeluje nějaká spojen í ci síť, přirozeně nas zaj ímá, jakou mame možnost se dostat odnekud nekam v tomto grafu. To ma mnoZstv í praktických motivac í -například poc ítacove, dopravn í, telefonn í c i potrubn ís íte. Je pochopitelne, Ze v takových sít ích chceme m ít možnost se dostat z každeho m ísta do každeho jineho.
Grafum s takovou vlastnost í ríkame souvislé.
Stručný přehled lekce
• Definice souvislosti grafu, vrcholová / hranová, vyšší souvislost.
• Algoritmus procházení grafem (souvislou komponentou).
• Eulerovske grafy.
Petr Hliněný,  FI MU Brno
FI: 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, .. ., e„,v„ ,
ve ktere vždy hrana ej ma koncové vrcholy vi-1, vj.
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 (vCetne cýklení). □
Lema 2.1. Mějme relaci ~ na množině vrcholu V(G) libovolného grafu G takovou, že pro dva vrcholy u ~ v pravé když existuje v G sled začínající v u a konCícíve v. Pak ~ je relací ekvivalence.
Důkaz. Relace ~ je reflexivní, nebot každy vrchol je spojeny sam se sebou sledem délky 0. Symetricka je take, protože sled ž u do v snadno obratíme na sled ž v do u. Stejne tak je ~ tranžitivní, protože dva sledy mUžeme na sebe navažat v jeden. □ □
Definice: Trídy ekvivalence výse popsane (Lema 2.1) relace ~ na V(G) se nažyvají komponenty souvislosti grafu G.
Jinak se taky komponentami souvislosti myslí podgrafy indukovane na techto trídach ekvivalence.
Petr Hliněný,  FI MU Brno_2_FI: MA010: Souvislost grafu
Připomenme si, Ze cesta v grafu je vlastne sledem bez opakovaní vrcholu.
Veta 2.2. Pokud mezi dvema vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. c
Důkaz. Necht u = v0, ei, vi,..., en, vn = v je sled delky n mezi vrcholy u a v v G. Zacneme budovat novy sled W z vrcholu w0 = u, ktery uZ bude cestou:
- Předpokladejme, Ze novy sled W uZ ma pocatek wn, ei, wi,..., wj (na zacítku i = 0, tj. jen wn bez hran), kde wj = v j pro nektere j G {0,1,..., n}. c
- Najdeme nejvetsí index k > j takovy, Ze vk = vj = wj, a sled W pokracujeme krokem ..., wj = vj = vfc, efc+i, wi+i = vfc+i,.... c
- Zbyva dokazat, Ze novy vrchol wj+i = vk+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo w; = wj+i, l < i, pak bychom na vrchol wj+i „přeskoali" uZ dříve z vrcholu w;, spor.
- Nakonec skoncíme, kdyZ wj = v. c
□
Ačkoliv uvedeny dukaz vypada slozite, je to jen jeho formálním zápisem. Ve skutečnosti se v důkaze nedeje nič jineho, neZ Ze se původní sled zkracuje o opakovane vrcholy, aZ nakonec zákonite vznikne cesta. Jeho výhodou je konstruktivnost - vidíme, jak cestu získat.
Petr Hliněný,  FI MU Brno_3_FI: MA010: Souvislost grafu
Důkaz kratší, ale nekonstruktivní, pro Větu 2.2:
Ze všech sledU mezi vrcholy u a v v G vybereme sled W s nejmenší dělkou. Je snadno vidět, Ze pokud W zopakuje nektery vrchol grafu G, mUZeme W jeste zkrátit, a to je
Zíverem se dostavame k nejduleZitejsí definici souvisleho grafu: Definice 2.3. Graf G je souvislý
pokud je G tvořený nejvyse jednou komponentou souvislosti, tj. pokud kaZde dva vrcholy G jsou spojene cestou (dle Vety 2.2).
Podívejte se, kolik komponent souvislosti ma tento graf:
spor s předpokladem. Proto je W cestou v G. c
□
•
Vidíte obe dve komponenty?
V
Petr Hliněný,  FI MU Brno
FI: MA010: Souvislost grafu
2.2   Prohledávání grafu
Pro vytvoření co nejobecnějšího schématu algoritmu pro procházení grafu vystačíme s nasleduj ícími datovými stavy a pomocnou strukturou:
• Vrchol: ma stavy ...
— iniciacn í-dostane na zacatku,
— nalezeny - pote, co jsme jej přes nekterou hranu nalezli,
— zpracovany - pote, co jsme uZ probrali vsechny hrany z nej vychazej íc í.
• Hrana: ma stavy ...
— iniciacn í-dostane na zacatku,
— zpracovana - pote, co uz byla probrana od jednoho ze svych vrcholu. c
• Úschovna: je pomocna datova struktura (mnozina),  
Poznámka: Způsob, kterým se vyb í rají vrcholy z úschovny ke zpracován í, určuje variantu algoritmu prochazen í grafu. V prohledavaných vrcholech a hranach se pak provadej í konkrétn í programove akce pro prohledan í a zpracovan i naseho grafu.
udrzuje nalezene a jeste nezpracovane vrcholy.
V
Petr Hliněný,  FI MU Brno
FI: MA010: 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 v0 grafu G}; stav(v0) = nalezený; while (U je neprázdna) {
vybrat v G U;     U = U\{v}; ZPRACUJ(v);
foreach (e hrana vycházející z v) {
if (stav(e)==iniciacní) ZPRACUJ(e);
w = opacny vrchol hrany e = vw;
if (stav(w)==iniciacní) {
}
}
G zpracovaný;
V
Petr Hliněný,  FI MU Brno
FI: MA010: Souvislost grafu
Způsoby implementace procházení grafu
• Procházení „do hloubky' - Úschovna U je implementovaná jako zásobník, tj. dále prohledáváme od posledních nalezených vrcholu. c
• Procházení „do šířky' - Úschovna U je implementovaná jako fronta, tj. dále prohledáváme od prvních nalezených vrcholu. c
• DijkstrUv algoritmus pro nejkratsí cestu - z Úschovný vybíráme vzdý vrchol nejblizsí k pocátecnímu v0. (Toto je dost podobne prohledávání do sířký, ale obecnejsí i pro prípadý, kdý hraný nejsou „stejně dlouhe".)
Tento algoritmus bude popsán v přístí lekci. c
Příklad 2.11. Ukázka průchodu následujícím grafem do hloubky z vrcholu a.
9
Petr Hliněný,  FI MU Brno
a<§>-
V b
FI: MA010: Souvislost grafu
Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezen í vrčholU, jsou tlustou čarou (tyto hrany často m ívaj í spečialn í vyznam v aplikač íčh sčhematu algoritmu). Nalezene vrčholy se poznaj í podle príčhoz í tluste hrany a zpračovane vrčholy jsou značene dvoj ím krouzkem.
r
2.3   Vyšší stupne souvislosti
V sítových aplikacích nas casto zajíma nejen, jestli se za normálních podmínek muzeme pohybovat mezi vrcholy/uzly, ale take, jake spojení muzeme nalezt v případe lokalních vypadku (odolnost a redundance).
Toto lze teoreticky podchytit zkoumáním „vyssích" stupnu souvislosti grafu. c
Definice: Graf G je hranové k-souvislý, k > 1, pokud i po odebraní libovolnych nejvyse k — 1 hran z G zustane vysledny graf souvisly. c
Definice: Graf G je vrcholové k-souvislý, k > 1, pokud i po odebran í libovolnych nejvyse k — 1 vrcholu z G zustane vysledny graf souvisly. Specialne uplny graf Kn je vrcholove (n — 1)-souvisly.
Pokud mluvíme jen o k-souvislem grafu, mame na mysli vrcholove k-souvisly graf. c
Strucne receno, vysoka hranova souvislost znamena vysoky stupen odolnosti síte proti vypadkum spojení-hran, neboli síl: zustane stále dosazitelna, i kdyz libovolnych k — 1 spojení bude preruseno. Vysoka vrcholova souvislost je mnohem silnejsím pojmem, znamena totiz, ze síť zustane dosazitelna i po vypadku libovolnych k — 1 uzlu-vrcholu (samozrejme mimo tech vypadlych uzlu).
Petr Hliněný,  FI MU Brr
FI: 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ů Ci hran zUstava souvislý. Z druhého grafu bychom museli odebrat nejmene 3 hrany, aby se stal nesouvislým, a proto je jeho hranova souvislost 3. Na druhou stranu vsak staCí odebrat 2 vrcholy, aby mezi jeho levým a pravým krajním vrcholem žadne spojení nezustalo. (Vidíte, ktere dva?) A jak je tomu u tretí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).
Mengerova věta
Důkaz následujícího důležitého výsledku by nebyl jednoduchý pri použití stávajících znalostí, proto jej ponecháme na pozdejSí lekce.. . („Toky v sítích".)
Věta 2.6. Graf G je hranově k-souvisly právě když mezi libovolnými dvěma vrcholy lze vest aspon k hranově-disjunktnách cest (vrcholy mohou být sdílené). Graf G je vrcholove k-souvislý prave když mezi libovolnými dvěma vrcholy lze vest aspon k disjunktních cest (mznych az na ty dva spojovaná vrcholy). c
Veta nám vlastně říká, ze stupeň souvislosti grafu se přirozeně rovná stupni redundance spojení vrcholu. Na výse uvedenem obrazku mezi kaZdými dvema vrcholy prvního grafu muZeme vest aZ 4 disjunktní cesty.
U druheho grafu treba mezi levým a pravám koncem lze vest jen 2 (vrcholove) disjunktní cesty, ale mezi kazdími dvema vrcholy lze vest 3 hranove-disjunktní cesty
Petr Hliněný,  FI MU Brr
FI:MA010: Souvislost grafu
V duchu predchoz í Mengerovy vety pokracujeme s nasleduj íc ími poznatky.
Věta 2.7. Necht G je vrcholově 2-souvisly graf. Pak kaěde dve hrany v G leží na spolecne kružnici. □
Důkaz: Nechť e, f G E (G). Sestroj íme graf G' podrozdelen ím obou hran e, f novymi vrcholy ve,vf. Je zrejme, ze i G' je vrcholove 2-souvisly graf, takze podle Vety 2.6 existuj í v G' dve disjunktn í cesty spojuj íc í ve s v f, tvorící spolu kruznici C'. Nakonec C' indukuje v G kruznici C prochazej íc í e i f. □ □
Rozs íren ím predchoz í uvahy lze dokonce dokazat:
Věta 2.8. Necht G je vrcholově k-souvisly graf, k > 1. Pak pro kaěde dve disjunktní množiny U\, U2 C V (G), \U\\ = \U2\ = k v G existuje k po dvou disjunktních cest z vrcholu Ui do vrcholu U2.
U2
•
Petr Hliněný,  FI MU Brr
FI:MA010: Souvislost grafu
2.4   Jedním tahem: Eulerovské grafy
Snad nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera -jedna se o slavných 7 mostů v Kralovci / Kónigsbergu / dnešním Kaliningrade.
O jaký problém se tehdy jednalo? Městští radní chtěli vědět, zda mohou suchou nohou přejít po kaZdém ze sedmi vyznaCených mostu pravě jednou.
Petr Hliněný,  FI MU Brn.
FI: MA010: Souvislost grafu
Rozbor tohoto problému vede k následující definici a odpovedi. Definice: Tah je sled v grafu bez opakování hran.
Uzavřený tah je tahem, který koncí ve vrcholu, ve kterem zaCal. Otevřený tah je tahem, který koncí v jinem vrcholu, neZ ve kterem zacal.
Nejstarší výsledek teorie grafů od Leonarda Eulera pote zní: c
Veta 2.9. Graf G lze nakreslit jedním uzavřeným tahem právě kdýZ G je souvislý a vsechný vrcholy v G jsoů sůdeho stůpne. c
Důsledek 2.10. Graf G lze nakreslit jedním otevřeným tahem prýve kdýZ G je souvislý a vřsechný vrcholý v G ařz na dva jsoů sůdýeho stůpnře.
Petr Hliněný,  FI MU Brr
FI:MA010: Souvislost grafu
Důkaz: Dokažujeme oba smery ekvivalence. Pokud lže G nakreslit jedním užavrenym tahem, tak je žrejme souvisly a navíc ma každy stupeň sudy, nebol: užavřeny tah každym pruchodem vrcholem „ubere" dve hrany.
Naopak žvolíme meži vsemi užavrenymi tahy T v G ten (jeden ž) nejdelsí. Tvrdíme, že T obsahuje vsechny hrany grafu G.
- Pro spor vežmeme graf G' = G — E(T), o kterem predpokladejme, že je nepraždny. Jelikož G' ma taktež vsechny stupne sude, je (ž indukcního předpokladu) libovolna jeho komponenta C C G' nakreslena jedním užavrenym tahem TC. □
- Vžhledem k souvislosti grafu G každa komponenta C C G' protína nas tah T v nekterem vrchole w, a tudíž lže oba tahy TC a T „propojit pres w". To je spor s nasím předpokladem nejdelsího možneho T. □
□
Důkaz dusledku: Nechť u,v jsou dva vrcholy grafu G mající lichy stupen, neboli dva (predpokladane) konce otevreneho tahu pro G. Do G nyní pridame novy vrchol w spojeny hranami s u a v. Tím jsme nas prípad prevedli na pňedchoží prípad grafu se vsemi sudymi stupni. □
Petr Hliněný,  FI MU Brr
FI: MA010: Souvislost grafu