Grafové algoritmy
2009/10, 1. térmín
1. Maximální párování
Je dán neorientovaný graf G = (V, E). Množina M C E je párování, pokud žádné dve různé hrany ž M nemají společný vrchol. Máximálitá párovaní se rožumí vžhledem k poctu hran.
Vrchol v G V je volny vzhledem k parování M, není-li koncem žádne z hran v M. Cesta P = (v0, vi,..., vk), k > 1, v G je střídává vžhledem k párovaní M, jsou-li vrcholy na ní po dvou ružne a strádajá-li se v ná hrany ž M a E \ M. Takova cesta je volná vžhledem k M, jsou-li oba jejá konce volne. Jejá álternácí dostávame párováná M', ktere se od M lisá prave tím, že pro libovolnou hranu e na P je e G M prave když e G M' a naopak.
a) Dokažte vetu:
Véta. M je maximální parovaní v G prave když v G neexistuje volna cesta vžhledem k M.
Požn. V dukažu netriviální implikace mužete uvážit dve párovaní M a M' a diskutovat jak vypadají souvisle komponenty grafu (V, M U M').
Ve žbytku pojednaní je graf G bipártitní, tj. existují nepraždne disjunktní množiny vrcholu X, Y davající ve sjednocení cele V a takove, že libovolna hrana ž E ma jeden konec v X a druhá v Y. Fixujme taková X, Y.
V náasledujáícáím algoritmu je Match[y] = x, je-li {x,y} G M a Match[y] = 0, je-li y volná vžhledem k M.
Jeho podstatou je hledaní volnách cest ž u G X pomocí BFS(G). Volne cesty ž v G Y nemusíme uvažovat (stací je opacne orientovat). Pro cestu (u,v,u',v',u",v",...) klademe Prev[v] = u, Prev[v'} = u',..Navstávene vrcholy ž X mame v poli Q[l], Q[2],... a ty ž Y množine N.
b) V uvedených algoritmech doplnte radky 18 resp. 4.
1
MaxMatching(G)
1 for i — 1 to n
2 Match[i] — 0
3 for u E X
4 Q[1] — u, Qsize — 1
5 N — 9
6 for i — 1 to n
7 Prev[i] — 0
8 k — 1
9 repeat
10 x — Q [k]
11 for y E Adj [x]
12 if y E N
13 přidej y do N
14 Prev[y] — x
15 if y je volný
16 Alternuj (y)
17 goto 1
18 přidej ......... do Q
19 k — k + 1
20 until k > Qsize
21 odstran z grafu vrcholy z Q a N vcetne incidentních hran
22 1:
Alternuj (y)
1 repeat
2 w — Prev[y]
3 Match[y] — w
4 ...
5 Match[w] — y
6 y — v
7 until y = 0
c) Doplňte důkaz věty :
Věta. MňoZiňa M = { {x, Match[x]} | x g X, Match[x] = 0 } je maximálním parovamm grafů G.
Důkaz. Pokůd Zádňý z X nezůstane volňý, máme maximální párování. Pokůd z u G X ňajdeme volňoů cestů, alternujeme ji. Pokůd z u G X existuje volňá cesta, ňajdeme ji, ňebot' pred r. 21 mame v Q vrcholy prave vrcholy z X dosazitelňe z u pomocá
..........................................................................zacíňající hraňoů...............................
a v mňoziňe N.......................................
Pokůd volňa cesta z u ňeexistůje, mame pred r. 21 :
2
(i) \Q\ = \N| +......................
(ii) každý vrchol z N je zpárován s .......................................................
(iii) neexistuje hrana mezi Q a Y \ N.
Zbývá ukazat, že vrcholy z Q a N as nimi incidentní hrany je možne „beztrestne" odstranit.
I kdyby jsme je neodstranili, nemuze v budoucnu vest volna cesta z u' G Q, u' = u, nebot'
Rovnez, kdyby takova cesta vedla z u' G X \ Q a nezůstala cela v X \ Q a Y \ N, navštívila
by nejprve nejake v G N pred tím nez by mohla do Q kvuli ...........................................
Pak by pokračovala do nejakeho
a pote do nejakeho
....................................................... , atd.,
a nemohla by skoncit v nejakem volnem vrcholu kvuli
- SPOR
d) Do prilozených diagramu vyznacte prubech algoritmu. Hrany aktualního parovýní znacte cervene, orientovane hrany (y, Prev[y]) znacte modre a odstranene vrcholy a hrany budou cerne (pozor : odstranena hrana muze být v parovíní). Nový obrazek kreslete, kdykoliv probehne nekterý z rýdku 7,16 (vyznacte jen zmeny),20. Muzete vynechat malovaní pro u = 5 a zacít s u = 6. Seznamy sousedu jsou serazeny podle velikosti ci abecedy.
Rovnez vyber u probíhý podle velikosti. Vyznacujte tez Q[1], Q[2],... ,Q[Qsize] a vrcholy yi,y2,... z radku 13 (ty se buduji' pro nove u znovu).
3
4
Dijkstrův algoritmus
Kontrolní otázky
a) Napište jednoduchý příklad orientovaného hranově ohodnoceného grafu G a jeho vrcholu s takoveho, že Dijkstrův algoritmus při hledání nej-kratších cest ž vrcholu s v grafu G nevýpoCíta správní výsledek. U každeho vrcholu uved'te jak správnou hodnotu nejkratsí cestý ž s do tohoto vrcholu, tak výsledek výpocítaný Dijkstrovím algoritmem.
b) Napiste jednoduchý príklad orientovaneho hranove ohodnoceneho grafu G a jeho vrcholu s takoveho, že: Graf G ma alespoň 4 vrcholý, alespoň jedna jeho hrana ma kladne a alespoň jedna hrana žaporne ohodnocení a Dijkstruv algoritmus pri hledaní nejkratsích cest ž vrcholu s v grafu G výpoňcítaí spríavnýí výísledek.
Výpočet
Pomocí Dijkstrova algoritmu naležnete nejkratsí cestý (a jejich delký) ž vrcholu s do vsech vrcholu žadaneho grafu. Abý býl vípocet prehlednejsí, tak pokažde, kdý je nejaký ukažatel n [v] žmenen ž nejakejo užlu (tj. ž hodnotý ružne od nit) na jiní užel, použijte k dalsímu vípoctu nový níže uvedený diagram. Vždý výžnacte aktualní hodnotý d[v] u vsech vrcholu v, již žpra-
1
cované vrcholy, pro které je hodnota vypočítána správně a hrany stromu indukovaného ukazateli n (nejlépe tak, jak je to v ilustračním príkladu v brožurce). Je-li v nektere iteraci na víber z více uzlu, vybírejte v abecedním poradí.
\3
•a
•e. -
\^^^     2 ^^^^ 3 b 1 c
-"  f . *-1-
\3
1
/
/
\   /   ,    \   /1
•k
•l
•m
<
1
1
2
\ 3
"""""" •a ^-""^ •h ^
•e -
■<- )
1
h
1 •l
//
•k
"""""" •a -"""^J" •-"
I ^^^^
•c
•e. -
3 l /
■<- )
1
h
- -1...................> '
f
■ •l
•a
o 1 ,/
-^""'^   3               \              1 c -" •h-" •
•e-4-5» f ^ "-1-•a-
/// X\\\  /// ^/
j • <-1--1 ....................>
1
h
•m
2
4
l
3
l
3
2
4
l
l
2
3
Grafové algoritmy
2009/10, 2. térmín
1. Maximálni cesta
Je dán souvislý neorientovaný graf G = (V, E). Terminologie a značení :
n =| V \, m =| E |,
deg(v) značí stupen vrcholu v G V,
místo {u, v} píšeme stručne uv,
(v0,vi,... ,vk) je cesta, je-li k > 0, v0,vi,...,vk jsou po dvou ruzne prvký z V a vovi,.. .,vk-ivk G E,
(v0,vi,..., vk) je kružnice, je-li k > 3, v0 = vk, v0,vi,..., vk-i jsou po dvou ruzne prvký z V a vovi,... ,vk-ivk G E,
Ta je hamiltonovská, je-li k = n.
V algoritmu se strídají čtýri faze :
1. Cestu P = (u,... ,v) rozsirujeme nadoraz doleva (začína se s P = (x)).
2. Cestu P = (u,... ,v) rozsirujeme nadoraz doprava.
3. Mame-li na ceste P = (u,... ,v) vrchol w takový, ze vw,uw+ G E,
P = (u,... ,w,w+,... ,v) (muze být w = u či w+ = v), modifikujeme P na kruznici C.
4. Kruznici C modifikujeme na cestu, ktera ma o jednu hranu více nez puvodní P.
Necht' x G V je pevne výbraný.
a) V nasledujícím algoritmu doplňte radký 6 a 12.
LongPath(G,x)
1 u    x, v     x, P (x)
2 repeat
3 whilé existuje w G V \ P splňující wu G E
4 přidej w zleva k P, u w
5 whilé existuje w G V \ P splňující wv G E
6 přidej w zprava k P, v w
7 for w ňa P
8 if wv G E aňd w+u G E
9 C     P + vw — ww+ + uw+
10 if C je hamiltonovská
11 goto 1
12 ňajdi z G C, y G C, zy G E
13 modifikuj C + zy ňa cestu P z y do z+
14 u    y, v z+
15 until zadňá zmeňa v prubehu tohoto cyklu
16 1:
1
Složitost : předpokládejme, že v konstantním čase dokážeme zjistit, zda dané w G V je na P či na C a přo dane p,q G V zda pq G E či nikoliv.
b) Doplnte úvahy v následujícím odhadu složitosti :
Faze 1 a 2. Množina vřčholú na P...........................
jsme jednou pou žili nebo odmáítli jistou hřanu
Přoto když
Tedy čelkem
přo vsečhny přúbehy fáží 1 a 2.
Faže 3. Na P přočhažíme možná w - tečh je to vežme..................... Takováčh P mame........
P ři uásp ečhu p řevřačáíme čáast P -....... Tedy čelkem v sečhny fáaže 3
vežmou
Fáže 4. Vybeř z přo danou faži 4 vežme
Celkem vábeř z přo vsečhny faže 4
vežme
Zjistení, žda dane z je vhodne vežme
Pokud jsme ž n ejakáeho z neusp eli, ne-
podaří se nam to ani nikdy v budoučnu. Tedy přo vsečhny faže 4 a přo vsečhna z potřebujeme
Celá algoritmus potřebuje...............................
č) Doplnte dukaž vety :
Veta. Nečht' přo každe u,v G V, u = v, uv G E mame deg(u) + deg(v) > n. Pak nas algotitmus najde hamiltonovskou křu žniči.
Důkaz. Připustme, že jsme nenaležli hamiltonovskou křužniči a že jsme skončili s čestou P = (u,... ,v) s, řekneme s k hřanami. P nemuže bát prodloužena že sáčh konču a přoto hřany ž u a v vedou
Dáale přo w na P maáme : vw G E dáa ........
Tedy hřany ž u mohou vest do maximalne
vřčholu. Tedy deg(u) < ....................,
čož dá deg(u) + deg(v) < ..........................
d) Do přiloženáčh diagřamu vyžnačte přubečh algořitmu. Dano x = 12. Vybeř w, z, y na ř. 3, 5, 12 řespektuje pořadí 1 < 2 < .... Vybeř w na ř. 7 přobíha po P žleva dopřava. Novy stav žačhyt'te vždy po provedení 5-6, 9, 13. P je želena, C je červena.
V sečhny fáaže 4 vežmou
SPOR
2
a
4
5
Minimální kostry
Kontrolní otázky
a) Napište jednoduchý příklad neorientovaného souvislého hranově ohodnoceného grafu s 5 vrcholy, který má přesne 6 různých minimainích koster.
b) Necht' n > 5 je libovolne, ale nadále pevne zvolene prirozene císlo. Napiste, kolik různých minimálních koster ma graf G = (V, E,w), kde V = {1,...,n}, E = {{i,i + 1} | 1 < i < n - 1} u {{n, 1}, {1,3}} a ohodnocení w({x,y}) = 1 pro libovolnou hranu {x,y} g E.
Výpočet
Pomocí Primová algoritmu naleznete nejakou minimílní kostru zadaneho grafu. Abý býl výpocet prehlednejsí, tak pokazde, kdý je nejaký ukazatel n [v] zmenen z nejakejo uzlu (tj. z hodnotý ruzne od nit) na jiný uzel, pouzijte k dalsímu vípoctu noví níiže uvedení diagram. Vzdý význacte pri tomto prechodu aktuílní hodnotý key[v] u vsech vrcholu v, hraný ktere jsou jiz soucastí minimílní kostrý a hraný, ktere jsou ve strome indukovanem ukazateli n, ale nejsou dosud soucístí minimalní kostrý (tj. jeden jejich vrchol dosud lezí ve fronte Q). Kvuli jednoznacnosti zacnete vípocet z vrcholu s a je-li v nektere iteraci na víber z více vrcholu, výbírejte v abecedním poradí.
1
I
I
•c
I
2 >>^">>i^~^\ 2
•f
•h
2 >>>>'>><l^^\ 1
-2
•i
•k
s
I
I
•c
I
2 >>>>>i^^^ 2
•f
h
2 >>>>'>><l^^\ 1
2
•i
•k
I
d
I
•c
I
2 >>>'>'>>l^^\ 2
f
h
2 >>>>">>i^^\ 1
2
•i
•k
1
2
2
s
1
2
2
s
1
2
2
s
2
I
I
•c
I
2 >>>>>i^\. 2
•f
•h
2 >>>'>'>><l^^\ 1
-2
•i
•k
s
I
I
•c
I
2 >>>>>i^^^ 2
•f
h
2 >>>>>><l^^\ 1
2
•i
•k
I
d
I
•c
I
2 >>>>>>l^^\ 2
f
h
2 >>>>">>i^^\ 1
2
•i
•k
1
2
2
s
1
2
2
s
1
2
2
s
3
Grafové algoritmy
2009/10, 3. termín
1. Bloky souvislého neorientovaného grafu
Je dán souvislý neorientovaný graf G = (V, E). Terminologie a značení : místo {u,v} píšeme stručne uv,
(v0,v1,... ,vk) je cesta, je-li k > 0, v0,v1,...,vk jsou po dvou ruzne prvky z V a VoVi,..., vk-\vk G E; často tez píseme (vovi,..., vk-1vk).
(v0,v1,..., vk) je kružnice, je-li k > 3, v0 = vk, v0,v1,..., vk-1 jsou po dvou ruzne prvky z V a vovi,.. .,vk-ivk g E,
Hrana e je most, kdyz po jejím odstranení graf prestívý být souvislý. Necht M značí množinu vsech mostu.
Na mnozine E \ M definujeme relaci ~ vztahem e ~ f prave kdyz hrany e, f lezí na nejake společne kruznici.
a) Doplnte dukaz.
Lemma 1. Relace ~ na mnozine E \ M je relací ekvivalence. Dukaz.
Bloky v G jsou nasledující podgrafy grafu G :
- most se svymi koncovími vrcholy,
- pro e G E \ M, trída e ~ spolu s konci jednotlivích hran.
Neprazdní mnozina hran B spolu s jejich koncovími vrcholy je bisouvisia, lezí-li její libovolne dve hrany na společne kruznici nebo jedna-li se o jedinou hranu.
b) Formulujte vztah mezi bisouvislími podgrafy a bloky (vse netriviílní) a vase tvrzení dokazte.
Lemma 2.
1
Následující algoritmus hledá bloky grafu G; přitom
Cuv je (jediná) kružnice vzniklá přidáním hrany uv ke stromu T - tzv. fundamentální kružnice pro hranu uv,
Buv ma bát blok obsahucící hranu uv, Q je fronta vrcholu - je to jako v BFS, T je BFS-strom.
c) V algoritmu doplnte rídky 12 a 15.
Blocks(G)
1 for uv G E
2 Buv — uv
3 vyber x G V
4 Q — x
5 repeat
6 u — head Q
7 for v G Adj u
8 if v G Q
9 pridej uv do T, pridej v na konec Q
10 else for xy G Cuv
11 Buv -     Buv U Bxy
12 for xy...........................
13 Bxy   - Buv
14 odstran u z Adj v
15 odstran u.......................
16 until Q = 0
d) Doplňte dukaz tvrzení :
Lemma 3. Po kazde iteraci cyklu 7-14 je kazde Buv bisouvisle. Dukaz. Indukcí vzhledem k poctu k jiz provedených cyklu.
k = 0. Libovolne Buv = ......................... a tedy............................................
Indukcní krok : 1. Necht' v G Q. Pak...........................
2. v G Q. Vytvorí se kruznice u,v = x0,x\,... ,xk = u, xoxi,... ,xk-\xk G T.
Pak B = ................................................je novou hodnotou pro Bxy, xy G ................
Necht' i G {1,... ,k}, ab G BXi_lXi. Pro ab = xi-1xi mame ab a uv na kruznici v B.
Pro ab = xi-1xi míme ab a xi-1xi ............................podle......................................
a podle.....................................míme ab a uv na kruznici v B.
Tranzitivita ~ da zbytek.
e) Doplnte dukaz tvrzení :
Veta. Po skoncení algoritmu je pro kazde uv G E graf Buv blokem obsahujícím hranu uv.
2
Důkaz. Připusťme, že Buv není blok. Nechť B je blok obsahující hranu uv. Máme Buv ^ B. Nechť xy G B \ Buv. Exisťuje kružnice C v B obsahující
Ukážeme, že xy G Buv a ťo bude spor.
Mužeťe použiť : Nechť' hrany z E \ T na C jsou e\,... ,ek. Nechť příslušne fundamenťainí kružnice jsou C\,...,Ck. Kružnice považujeme ža sousední, mají-li spolecnou hranu. Lže ukažať, že ťakovyťo graf (s vrcholy C\,..., Ck) je souvislí.
f) Demonsťrujťe algoriťmus na paníckovi níže. Uved'ťe ťabulku, v nížž radky odpovídají žmením Q. Do prvního sloupce píseme akťuílní Q, pokud se neco pridavalo do T, uved'ťe ťo do 2. sloupce. Do 3. sloupce píseme žmenene Cuv a Buv. Míme x = 1 a sežnamy sousedu jsou usporadany podle velikosťi ožnacení sousedu od nejmensího po nejveťsí. V diagramu žnažorneťe bloky.
3
Silně souvislé komponenty
Kontrolní otázky
a) Napište jednoduchý příklad orientovaného grafu, který má 5 silne souvislých komponent, avšak zmenou orientace jedne hraný (tzn. otoCením jedne šipký) klesne poCet silne souvislých komponent na 1. Príslušnou hranu v grafu význacte.
b) Napiste jednoduchý príklad orientovaneho grafu, který ma 5 silne souvislých komponent, avsak zmenou grafu na neorientovaný graf (tzn. Ze ke kazde hrane pridame opacne orientavanou hranu, pokud tato v grafu neexistuje) získame graf, který mý 3 (silne) souvisle komponentý.
Výpočet
Na následujícím grafu nejprve proved'te prohledání do hloubky (DFS). Kvůli jednoznačnosti zaCnete prohledávat z vrcholu s, pokud máte v nekterém kroku na váber, rozhodujte se dle abecedy (tzn. seznamy sousedu jsou usporadany podle abecedy). Vyznačte hrany patricí do DFS stromu a ke kazdemu vrcholu x napiste hodnoty d[x] a f [x] (tzv. discovery a finishing time).
1
mu-„ mv
Nyní vhodným prohledáním transponovaného grafu najděte silně souvislé komponenty původního grafu. Opět platí, že transponovaný graf má seznamy následníku serazene dle abecedy. K dispozici mate diagram původního grafu, nezapomeňte tedy, že tentokrít prochazíme graf proti smeru sipek. Opet vyznaCte hrany patrící do DFS stromu, hodnoty d[x] a f [x] pro vsechny vrcholy x a samozrejme tez nalezene silne souvisle komponenty.
2
s
/ \
c
•d:
f
\ /
n
Z \
/
/
/
/
v
•d
•s \
^a -3- #b -3» ^c
^\ V'\\.f ^
-3- ^ \-
j -> •r
Z \
n
i
y i /
/
/
/
/
u
v
3