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).
• Silná souvislost orientovaných grafů.
• Eulerovské tahy v grafu.
Petr Hliněný,  Fl MU Brno, 2012
1/21
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,... ,en,vn , ve které vždy hrana     má koncové vrcholy ví-i,ví.
Sled je vlastně procházka po hranách grafu z u do u. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). □
Letna 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í v u a končící ve v. Pak ~ je relací ekvivalence.
Důkaz. Relace ~ je reflexivní, nebot 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 v do u. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. C
Petr Hliněný,  Fl MU Brno, 2012
2/21
FI:MA010: Souvislost grafu
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ípodgrafy indukované na těchto třídách ekvivalence.
Podívejte se, kolik komponent souvislosti má tento graf:
Vidíte v obrázku všechny tři komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfním K 2) a třetí je to zbývající.
Petr Hliněný,  Fl MU Brno, 2012
3/21
FI:MA010: Souvislost grafu
Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů.
Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta.
Důkaz. Nechť u — vq, e±, t>i,..., en, vn — v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu wo — u, který už bude cestou:
- Předpokládejme, že nový sled W už má počátek wo, e±, u>\,Wi (na začátku i — 0, tj. jen wo bez hran), kde Wi — Vj pro některé j e {0,1,..., n}. □
- Najdeme největší index k > j takový, že V]~ — Vj — Wi, a sled W pokračujeme krokem ..., wt = v j = vk, ek+i, wl+1 = vk+i,.... □
- Zbývá dokázat, že nový vrchol w^+i = ffc+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo wi — Wí+i, l < í, pak bychom na vrchol Wí+i „přeskočili" už dříve z vrcholu wi, spor.
- Nakonec skončíme, když Wi — v. □
C
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.
Petr Hliněný,  Fl MU Brno, 2012
4/21
FI:MA010: Souvislost grafu
Důkaz kratší, ale nekonstruktivní, pro Větu 2.2:
Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta.
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. □ C
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).
Petr Hliněný,  Fl MU Brno, 2012
5/21
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 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 (a odložili ke zprac),
— zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející.
— (Případně ještě stav „post-zpracovaný", po dokončení všech následníků.)
• Hrana: má stavy .. .
— iniciační - dostane na začátku,
— zpracovaná - poté, co už byla probrána od jednoho ze svých vrcholů. □
• Úschovna: je pomocná datová struktura (množina),
— udržuje odložené, tj. nalezené a ještě nezpracované vrcholy.
Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu. Zde pro větší obecnost dokonce v úschovně udržujeme vrcholy spolu s příchozími hranami. 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.
Petr Hliněný,  Fl MU Brno, 2012
6/21
FI:MA010: Souvislost grafu
Algoritmus 2.4. Generické procházení souvislé komponenty G 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 = {(0, vrj)}, pro libovolný vrchol vo grafu G; strom prohledávání T = 0; while (U je neprázdná) {
zvolit (e,v) G U;
U = U\{(e,v)};
if (e^0) ZPRACUJ (e);
if (stav(v) ^ zpracovaný) {
foreach (f hrana vycházející z v) { w = opačný vrchol hrany f — vw;
if (stav(w) ^ zpracovaný) (*) U = U u{(f ,w)};
}
ZPRACUJ(v);
stav (v) = zpracovaný;
T = T u{e,v};
}
}
G je zpracovaný;
Petr Hliněný,  Fl MU Brno, 2012
7/21
FI:MA010: Souvislost grafu
Algoritmus 2.5. Některé implementace procházení grafu;
tj. konkrétně implementace kroku „zvolit (e,v) e U" úschovny U.
• Procházení „do šířky", BFS - úschovna Uje implementovaná jako fronta, neboli je voleno (e,v) E U od prvních vložených do úschovny. □
• Procházení „do hloubky", DFS - úschovna Uje implementovaná jako zásobník, neboli je voleno (e,v) E U od posledních vložených do úschovny. □
• Dijkstrův algoritmus pro nejkratší cestu - z úschovny vybíráme vždy vrchol nejbližší k počátečnímu t>o. (Toto je dost podobné prohledávání do šírky, ale obecnější i pro případy, kdy hrany nejsou „stejně dlouhé".) □
Příklad 2.15. Ukázka průchodu následujícím grafem do šířky z vrcholu a.
Značení v prohledávaném grafu: barevně aktuálně zpracovávaný vrchol a jeho hrany objevující nové vrcholy, kroužkem a plnou čarou již zpracované vrcholy a hrany, tlustě výsledný strom prohledávání.
Petr Hliněný,  Fl MU Brno, 2012
9/21
FI:MA010: Souvislost grafu
Vidíte rozdíly tohoto průchodu proti předchozímu příkladu?
□
2.3   Vyšší úrovně souvislosti
V sítový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. □
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ý. □
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. 1-souvislý graf je pouhé synonymum pro souvislý.
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 — 1 uzlů-vrcholů (samozřejmě mimo těch vypadlých uzlů).
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?n
Věta 2.6. 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ý 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.7. 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.
V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky.
Věta 2.8. Nechí G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici.
Důkaz: Nechť e, / G E (G). Sestrojíme graf G' podrozdělením obou hran e,f novými vrcholy ve,Vf. Je zřejmé, že i G' je vrcholově 2-souvislý graf, takže podle Věty 2.7 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 /. C
Rozšířením předchozí úvahy lze dokonce dokázat:
Věta 2.9. Necht G je vrcholově k-souvislý graf, k > 1. Pak pro každé dvě disjunktní množiny U\,U2 c V (G), \Ui\ — IÍ/2I — k v G existuje k po dvou disjunktních cest z vrcholů Ui do vrcholů U2-
2.4   Souvislost v orientovaných grafech
Začneme analogicky Oddílu 2.1.
Definice: Orientovaným sledem délky n v orientovaném grafu D rozumíme střídavou posloupnost vrcholů a orientovaných hran
vo,ei,vi,e2,v2,... ,en,vn ,
ve které vždy hrana     míří z vrcholu ví-i do vrcholu t^. □
Věta 2.10. Pokud mezi dvěma vrcholy grafu D existuje orientovaný sled, pak mezi nimi existuje orientovaná cesta.
Pohledy na orientovanou souvislost
Prvním možným pohledem na souvislost orientovaných grafů je prostě požadovat grafovou souvislost po „zapomenutí" směru šipek. Toto se nazývá slabá souvislost.a
Jiný přístup je následovný:
Definice: Orientovaný graf D je dosažitelný směrem ven, pokud v něm existuje vrchol v e V (D) takový, že každý vrchol x G V (D) je dosažitelný orientovaným sledem z v.
Podrobným zkoumáním následujícího obrázku zjistíme, že tento graf není dosažitelný směrem ven, neboť chybí možnost dosáhnout vrchol b úplně vpravo. Na druhou stranu po vypuštění b je zbylý graf dosažitelný ven z vrcholu a vlevo.
Nakonec „symetrizací" přístupu dosažitelnosti se dobereme definici tzv. silné souvislosti, která je nejčastěji zmiňována u orientovaných grafů.
Letna 2.11. Nechí « je binární relace na vrcholové množině V(D) orientovaného grafu G taková, že uk, v právě když existuje dvojice orientovaných sledů - jeden z u do v a druhý z v do u v grafu D. Pak « je relace ekvivalence. □
Definice 2.12. Silné komponenty orientovaného grafu D jsou třídy ekvivalance relace « z Lematu 2.11. □
Orientovaný graf D je silně souvislý pokud má nejvýše jednu silnou komponentu.
Pro ilustraci si uvedeni následující příklad orientovaného grafu vlevo, jenž má čtyři vyznačené silné komponenty.
Kondenzace orientovaného grafu
Definice: Orientovaný graf, jehož vrcholy jsou tvořeny jednotlivými silnými komponentami orientovaného grafu D a šipky vedou právě mezi těmi dvojicemi různých komponent, mezi kterými vedou hrany v D, nazveme kondenzací grafu D. □
Definice: Orientovaný graf D je acyklický, pokud neobsahuje or. cyklus. □
Tvrzení 2.13. Kondenzace každého orientovaného grafu je acyklický orientovaný graf.
2.5   Jedním tahem: Eulerovské grafy
Pravděpodobně nejstaršízaznamenaný výsledek teorie grafů pochází od L. Eulera -jedná se o slavných 7 mostů v Královci / Kónigsbergu / dnešním Kaliningradě.
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.
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.
Onen slavný výsledek teorie grafů od Leonarda Eulera poté zní:
Věta 2.14. 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.15. GrafG 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ě.
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. □
C
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. C