Petr Hliněný, FI MU Brno 1 FI: MA010: Souvislost grafu
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é.
2
Stručný přehled lekce
* Definice souvislosti grafu, vrcholová / hranová, vyšší souvislost.
* Algoritmus procházení grafem (souvislou komponentou).
* Eulerovské grafy.
Petr Hliněný, FI MU Brno 2 FI: MA010: Souvislost grafu
2.1 Spojení vrcholů, komponenty
Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran
v0, e1, v1, e2, v2, . . . , en, vn ,
ve které vždy hrana ei má koncové vrcholy vi-1, vi.
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í). 2
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í v u 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 v do u. Stejně
tak je  tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. 2 2
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.
Petr Hliněný, FI MU Brno 3 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. 2
Důkaz. Nechť u = v0, e1, v1, . . . , en, vn = v je sled délky n mezi vrcholy u a v v G.
Začneme budovat nový sled W z vrcholu w0 = u, který už bude cestou:
­ Předpokládejme, že nový sled W už má počátek w0, e1, w1, . . . , wi (na začátku
i = 0, tj. jen w0 bez hran), kde wi = vj pro některé j  {0, 1, . . ., n}. 2
­ Najdeme největší index k  j takový, že vk = vj = wi, a sled W pokračujeme
krokem . . . , wi = vj = vk, ek+1, wi+1 = vk+1, . . .. 2
­ Zbývá dokázat, že nový vrchol wi+1 = vk+1 se ve sledu W neopakuje. Pokud by
tomu ale tak bylo wl = wi+1, l  i, pak bychom na vrchol wi+1 "přeskočili" už
dříve z vrcholu wl, spor.
­ Nakonec skončíme, když wi = v. 2
2
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ý, FI MU Brno 4 FI: MA010: 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. 2 2
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ý jedinou 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:
s s
s
s
ss
s
s
s
s
s s
2
Vidíte obě dvě komponenty?
Petr Hliněný, FI MU Brno 5 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,
­ 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ů. 2
* Ú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.
Petr Hliněný, FI MU Brno 6 FI: MA010: Souvislost grafu
Algoritmus 2.4. Procházení souvislých komponent grafu
Algoritmus projde a zpracuje každou hranu a vrchol grafu G.
vstup < graf G;
stav(všechny vrcholy a hrany G ) = iniciační;
uschovna U = {libovolný vrchol v0 grafu G};
stav(v0) = nalezený;
while (U je neprázdná) {
vybrat v  U; U = U \ {v};
ZPRACUJ(v);
for (e hrany vycházející z v) {
if (stav(e)==iniciační) ZPRACUJ(e);
w = druhý vrchol e = vw;
if (stav(w)==iniciační) {
stav(w) = nalezený;
U = U {w};
}
stav(e) = zpracovaná;
}
stav(v) = zpracovaný;
if (U je prázdná && G má další komponenty)
U = {lib. vrchol v1 další komponenty G};
}
Petr Hliněný, FI MU Brno 7 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 vrcholů. 2
* Procházení "do šířky" ­ úschovna U je implementovaná jako fronta, tj. dále
prohledáváme od prvních nalezených vrcholů. 2
* Dijkstrův algoritmus pro nejkratší cestu ­ z úschovny vybíráme vždy vrchol nejbližší
k počátečnímu v0. (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. 2
Příklad 2.5. Ukázka průchodu následujícím grafem do hloubky z vrcholu a.
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h i
j
Petr Hliněný, FI MU Brno 8 FI: 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.
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
ff 2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f ff 2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
ff
2
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
f
ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
f
fff
2
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
f
ff
ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
f
ff
f ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f
f
ff
f f
fff
2
Petr Hliněný, FI MU Brno 9 FI: MA010: Souvislost grafu
Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a.
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
ff 2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f ff 2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
ff
2
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f f ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f f f
ff
2
s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f f f
fff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f f f
ff ff
2 s s
s
s
ss
s
s s
s
a f b
c
d
ef
g
h
i
j
f f
f f f
ff f
fff
Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu
příkladu? 2
Petr Hliněný, FI MU Brno 10 FI: MA010: Souvislost grafu
2.3 Vyšší stupně souvislosti
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. 2
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ý. 2
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 - 1)-souvislý.
Pokud mluvíme jen o k-souvislém grafu, máme na mysli vrcholově k-souvislý graf. 2
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ů).
Petr Hliněný, FI MU Brno 11 FI: MA010: Souvislost grafu
s s
s
s
s
s s
ss
s s
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?)
Petr Hliněný, FI MU Brno 12 FI: MA010: Souvislost grafu
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). 2
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.
Petr Hliněný, FI MU Brno 13 FI: MA010: Souvislost grafu
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. 2
Důkaz: Nechť e, f  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 f. 2 2
Rozšířením předchozí úvahy lze dokonce dokázat:
Věta 2.9. Nechť G je vrcholově k-souvislý graf, k  1. Pak pro každé dvě disjunktní
množiny U1, U2  V (G), |U1| = |U2| = k v G existuje k zcela disjunktních cest z
vrcholů U1 do vrcholů U2.
Petr Hliněný, FI MU Brno 14 FI: MA010: Souvislost grafu
2.4 Jedním tahem: Eulerovské grafy
Definice: Tah je sled v grafu bez opakování hran.
Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal.
Nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera:
(Slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningradě.) 2
Věta 2.10. 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ě. 2
Důsledek 2.11. 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ě.
Petr Hliněný, FI MU Brno 15 FI: 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. 2
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  G
nakreslená jedním uzavřeným tahem TC. 2
­ Vzhledem k souvislosti grafu G existuje vrchol w incidentní zároveň s hranami
našeho tahu T i vhodné komponenty C  G
; tudíž lze oba tahy T a TC ,,propojit
přes w . To je spor s naším předpokladem nejdelšího možného T . 2
2
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. 2