Hranově a uzlově ohodnocen0 grafy
Def:   Nechť V, Hy, H e jsou množiny, E CV2,hv :V -> Hv,hE : E -> Čtveřici (V, £7, hy,riE) nazýv/Emeuz/ové a hranově ohodnocený orientovaný graf.
Vynech/Ením hranov0ho ohodnoceny dostaneme uzlově ohodnocený orientovaný graf (V,E,hv).
Vynech/Ením uzlov0ho ohodnocenfoy dostaneme hranově ohodnocený orientovaný graf (V,E,hE)-
Nepřipustíme-li v množině E dvojice tvaru (x, x), m/Eme (ohodnocen0) orientovan0 grafy bez smyček.
150
Def:   Nechť V, Hy, H e jsou množiny, E je nějak/E množina dvouprvkových a jednoprvkových podmnožin množiny V, hy : V —> Hy, He ' E —> Čtveřici (V, £7, hy,hE) nazýv/Emetyz/ové a hranově ohodnocený neorientovaný graf.
Vynech/Ením hranov0ho ohodnoceny dostaneme uzlově ohodnocený neorientovaný graf (V,E,hv).
Vynech/Ením uzlov0ho ohodnocenfoy dostaneme hranově ohodnocený neorientovaný graf (V,E,hE)-
Nepřipustíme-li v množině E jednoprvkov0 množiny, dost/Ev/Eme (ohodnocen0) neorientovan0 grafy bez smeček.
151
Pozn/Emka: Obecnější definice grafu připouští, aby množina hran E nebyla podmnožinou V (resp. množiny všech dvouprvkových a jednoprvkových podmnožin množiny V), ale aby to byla libovoln/E koněn/E množina, a je navíc d/Eno zobrazena : E     V , kter0 učuje, mezi kterými uzly dan/E hrana vede. Není-li zobrazenie injektivní, hovoří se o tzv. multigrafu.
Implementace
Graf lze reprezentovat maticísousednosti: neohodnocený graf G = (V, E) na n uzlech je reprezentov/Erčtvercovou maticí G = [gij]1<i<n 1<j<n nu' a jedniček tak, že gij = 1, pr/EĚ když (ij) G E.
Je-li graf hranově ohodnocený, G = (V, E, Iie), He ' E —> He, jsou v matici sousednosti přímo hodnoty hran: pro        G E \e gij = h(i,j), pro        ^ E \e gij = v, Wóev £ He-
J
152
Pro tzv. řfdk0grafy tj. grafy, v nichž počet hran je v o(n2), je výhodn/E reprezentace pomocí množin sousedů: neohodnocený graf G = (V, E) na n uzlech je reprezentov/En posloupností [si,... , sn] množin n/Esledníků každ0ho uzlu. Jsou-li>i,..., všichni n/Esledníci uzluu (tj. uzly, do nichž vede z u hrana), je su —       ..., v^}.
Nejčastější reprezentace posloupnosti množin sousedů je polem seznamů. Je-li graf uzlově ohodnocený, obsahuje i-tý prvek pole G dvojici (s^, hy(i)). Je-li graf hranově ohodnocený, obsahuje j-tý prvek i-t0ho seznamuj dvojici (vj,hE(i,Vj))-
J
153
Proch/Ezení grafu
Probl0m: Projít systematicky všechny uzly grafu.
Proch/Ezení grafu do hloubky
Algoritmus df s {depth-first search)
G=(V,E),   y = {l,...,n}, WCV
Budeme označovat všechny navštíven0 uzly pomocí procedurymark.
Na zač/Etku jsou všechny uzly nenavštíven0n(arked(^) = False).
Pro každý uzel u je Successors (u) seznam uzlů - n/Esledníků uzluu.
Vych/Ezíme z uzlů z množinyW a postupujeme st/Ele d/EI po hran/Ech do dosud
nenavštívených uzlů.
Cesty z označených do nově navštívených uzlů tvoří les s kořeny ve W.
Proch/Ezeni grafu do hloubky - imperativni pseudokod
procedure dfs (G:Graph; var W:Nodeset; var P:Nodearray) ; procedure dfsl (u:Node); begin
if not marked (u)
then begin mark (u);
for v G Successors (u) do begin P[v]   := u; dfsl (v)
end
end
end;
155
begin {dfs} for u G V do begin unmark (u);
P [u]   : = empty-end;
for u G W do
if not marked (u) then dfsl (u) end;
Chceme-li projít do hloubky všechny uzly grafu G = (V, E), položíme W = V.
Věta:   Algoritmus df s navštíví všechny uzly grafu dosažiteln0 z uzlů z množiny W.
Důkaz je zřejmý a plyne z toho, že se opakovaně označují všechny uzly, kter0 dosud označeny nebyly. Množina neoznačených uzlů se zmenšuje, takže algoritmus konverguje.
Pozn/Emka: Algoritmus funguje stejně pro orientovan0 i neorientovan0 grafy.
_)
Pozn/Emka: Algoritmus obecně není deterministický, protože nemusí být (a nebýv/E) specifikov/Eno poadí uzlů v množin/EchSuccessors(u) ani v množině W. Proch/Ezení grafu do hloubky tedy neurčuje pořadí navštívených uzlů jednoznačně.
Cvičení:   Nechť G = (V, E) je neorientovaný graf, V = {1, 2, 3,4, 5, 6}, E = {{1, 2}, {2,3}, {4,5}, {5,6}, {1,4}, {2,5}, {3,6}}, W = {1}. Jak/E jsou všechna možn/E pádí navštívených uzlů při vol/Enídf s (G, W) ?
Pozn/Emka: Významnou praktickou aplikací algoritmu df s je nalezení tzv. silně souvislých komponent orientovan0ho grafu.
Proch/Ezení grafu do šiky
Řešíme probl0m Projít systematicky všechny uzly grafu G = (V, E) dosažiteln0 (orientovanou) cestou z někter0ho z poč/Etěních uzlů zadaných množinou W C V.
Algoritmus bf s (breadth-first search) proch/Ezí uzly v jin0m pfcadí než při prohled/Ev/Ení do hloubky: uzly kter0 leží blíže poč/Etěním uzlům (uzlům, v nichž proch/Ezení záín/E), jsou navštíveny dříve než uzly ležící d/Ele od po/Etěních uzlů.
Pomocn0 datov0 struktury: frontaQ uzlů, les nejkratších cest (uložený v poli P) Navštíven0 uzly se opět označují pomocí procedury mark, uzel u bude označen, pr/Eé když marked(^) = True.
158
Proch/Ezeni grafu do snky - imperativni pseudokod
procedure bfs (G:Graph; var W:Nodeset; var P:Nodearray); var Q:Queue;
procedure bfsl (q:Queue);
begin while not (isempty(q)) do begin u := headq(q); dequeue(q);
for v G Successors (u) do if not (marked(v))
then begin mark (v);
enqueue (v,q); P[v]   := u
end
end end{bfsi};
159
begin {bfs}
for u G V do begin unmark (u);
P[u]   := empty-end;
Q := emptyq; for u G W do begin   mark (u);
enqueue (u,Q)
end; bfsl (Q) end {bfs}
Korektnost proch/Ezení grafu do šiky
Def: D0lkou sledu{v hranově neohodnocen0m grafu) rozumíme počet hran na tomto sledu.
Vzd/Elenost z uzluu do uzlu v je d0lka minim/Elního sledu vedoucího z uz\w do uzlu v, pokud takový sled existuje; pokud z uzlu u do uzlu v ž/Edný sled neexistuje, pak vzd/Elenost položíme+oo.
V neorientovan0m grafu mluvíme stručně o vzd/Elenosti mezi uzlyu a v.
J
161
Věta:   Nechť G — (V, E), s,u,v E V a nechť vzd/Elenost zs do u je menší než vzd/Elenost zs do v. Pak uzel u bude při výpočtu bf s(G,{s}) označen dříve než uzel v.
Důkaz: Stačí uk/Ezat, že do frontyQ jsou vžy přid/Ev/Eny uzly s aspbtak velkou vzd/Eleností ods, než jakou měl poslední přidaný uzel. To však lehce plyne indukcí podle vzd/Elenosti od uzlus.
Věta:   Nechť G = (V, E), s E V. Pak po provedení výpočtu bf s(G ,{s}) jsou navštíveny pr/Eě všechny uzly, do nichž vede z uzlu s (orientovan/E) cesta.
Důkaz: Indukcí podle vzd/Elenosti od uzlus.
162
Složitost proch/Ezení grafu do šiky
Věta: Nechť G — (V, E) je graf a W C V je množina poč/Etěních uzlů (vstupního stupně 0). Pak d0lka výpočtu bf s(G, W) v nejhorším případě je v 0(| W| + \E\).
Důkaz věty: Každý uzel bude označen a zařazen do fronty a u všech uzlů z fronty se pt/Eme na označenost jejich n/Esledníků. Tedy d0lka výpčtu bude jistě v Í2(\E\). Jelikož zařazujeme do fronty všechny uzly z W, je d0lka výpočtu tak0 vf2(\W\).Z těchto dvou faktů vyplýv/E, žejevJ2(|£|) fi Í2(\W\) = Í2(\W\ + \E\).
Do fronty zařazujeme jen uzly, kter0 až do t0 doby nebyly oznáenO, a přitom je hned označíme. Odtud plyne, že každý uzel je do fronty zařazen jen jednou. Tedy vnější cyklus while proběhne 0(| W| + |i£|)-kr/Et. Test ve vnřhím cyklu for proběhne vždy tolikr/Et, kolik hran vych/Ezí z uzlu, dohromady tolikr/Et, kolik m/E celý graf hran. Odtud opět dost/Ev/Eme, že d0lka výptw je v 0(\W\ + \E\ + \E\) = 0(\W\ + \E\).
Dohromady dost/Ev/Emé^(|l/|^| + |£ľ|), čímž je tvrzení dok/Ez/Eno
Minim/Elní kostra grafu
Def: Nechť G — (V, E,Iie), riE ' E —> R, je hranově ohodnocený neorientovaný graf. Faktor grafu G je podgraf F = (V, Ef, Yíe\e') 9r^fu G.
Def:   Takový faktor grafu G, který je strom, se nazýv/Ekostra grafu G.
Def:   Nechť G je souvislý neorientovaný graf s číselně ohodnocenými hranami. Kostra grafu G, kter/E m/E ze všech jeho koster nejmenší sonet hranových ohodnocení, se nazýv/Eminim/Elní kostrag rafu G.
Pozn/Emka: Kostry mají jen souvisl0 grafy, protože kostra musí podle déinice být strom. Tento požadavek však není z/Esadní a étšinu oevah o kostr/Ech Izeřpn0st i na nesouvisl0 grafy: stačí uvažovat zvl/Ešť kostru každ0 komponenty.
164
Cvičení:   M/Eme neorientovaný graC? = (V, E), V = {1, 2, 3,4}, E = {{1,2}, {2,3}, {3,4}, {4,1}, {1,3}}.
Kolik m/E tento graf podgrafu, faktoru a koster? V každ0m záchto tří případů spočítejte, kolik je všech podgrafů (faktorů, koster), a kolik z nich je navz/Ejem neisomorfních
Generický algoritmus pro nalezení minim/Elní kostry
Probl0m: Je d/En souvislý hranol ohodnocený neorientovaný graf G — (V, E^He)-Úkolem je nal0zt jeho minim/Elní kostru.
type SpT = Set of Edges;
proceduře genericMST (G:Graph; var A:SpT); begin
A := 0;
while A ještě netvoří kostru do begin
najdi hranu {u, v} bezpečnou vzhledem k A; A := Au{{u,v}} end
end
_J
Def:   Nechť G je souvislý hranově ohodnocený graf a A takový jeho podgraf, že A je podgrafem nějak0 minim/Elní kostry grafu G. Pak každ/E hrana zG — A, kter/E leží v minim/Elní koale T, se nazýv/E6ezpec/7/^/zhledem k A.
Def:   Nechť G = (V, E) je graf, Vi C V, V2 C F, Vi ^ 0, F2 ^ 0, Vi U F2 = V, Vi H V2 — 0- Pak množině
C = {{x,y}G£;|xG Vi.yGV^}
řík/E m erez grafu G.
Je-li navíc G' — (V7, E1\ h!) podgraf grafu G takový, že V' C V\ nebo V' C V2, řík/Eme, žeřez (7 respektuje podgraf G'.
_)
Věta:   Nechť G — (V, E, h e) je souvislý hranově ohodnocený neorientovaný graf, He ' E —> R. Nechť množina hran A C E \e obsažena v nějak0 minim/Elní košfe grafu G, nechť C je řez respektující podgraf indukovaný hranami z A a nechť
i>} G (7 je hrana s minim/Elním ohodnocením vC. Pak hrana {u, v} je bezpečn/E vzhledem k A.
Důsledek:   Nechť G = (V, je souvislý hranově ohodnocený neorientovaný
graf, množina hran A C E \e obsažena v nějak0 minim/Elní košfe grafu G a nechť T je nějak/E souvisl/E komponenta v les^V, A). Pak každ/E hrana spojujícíT s nějakou jinou komponentou v lese (V, A) a mající minim/Elní ohodnocení je bezpěn/E vzhledem kA.
167
Kruskalův (Borůvkův-Kruskalův) algoritmus
Je d/En hranoě ohodnocený neorientovaný graf G — (V, E^He), hled/Eme množinu hran A C E tvořící minim/Elní kostriíT = (V, A, He\a)-
type SpT = Set of Edges;
Component = Set of Nodes; {„vhodně reprezentovan/E" množine-procedure kruskal (G:Graph; var A:SpT); var W: Set of Component; begin A := 0; W := 0;
for v   e   V do W := WU{{v}}; seřadíme množinu E podle ohodnocení; for (u, v)   G  E {v pořadí od nejníže ohodnoceny do if WU^=WV {tj. u, v leží v různých komponent/Ecŕ} then begin A := A U {(u, v)};
sjednotíme obě tyto komponenty
end
end
Korektnost Kruskalova algoritmu
Věta:   Po skončení výpočtu kruskal(G, A) je v A množina hran grafu G tvořících jeho minim/Elní kostru.
Důkaz vyplýv/E z pedchozího Důsledku. Složitost Kruskalova algoritmu
Složitost algoritmu z/Evisí na datov0 struklíe reprezentující množinu komponent W. Pro reprezentaci komponent lesa můžeme použít tzv. binomi/Elih haldy. Dotaz WU^WV vyj/E<9íme dotazem, zda halda, v níž se nach/Ezí uzelu, je shodný s haldou, v níž se nach/Ezí uzelľ. Tento dotaz m/E logaritmickou složitost.
Složitost takto implementovan0ho Kruskalova algoritmu jepak 0(m log m), kde rn — E .
169
Primův algoritmus
Podobně jako Kruskalův algoritmus je Primův algoritmus speci/Biiím případem generick0ho algoritmu pro hled/Ení minim/Elní kostry. Zatoo však u Kruskalova algoritmu tvoří množina hran A v každ0m kroku les, v případě Primová algoritmu tvoří vždy strom (tj. souvislý les).
Odtud vyplýv/E, že na rozdíl od Kruskalova algoritmu požadavek souvislosti vstupního grafu je podstatný.
Protože strom začín/Eme budovat v učit0m mísš grafu, je souč/Estí vstupních dat ějaký pevně zvolený uzel r.
170
Vstup: souvislý hranově ohodnocený neorientovaný graf G — (V, E^íie), uzel r E V. Výstup: minim/Elní kostráT = (V, A, He\a) určen/E vektorem pedchůdců P.
type Node = 1. .n;
SpT = Array [Node] of 0..n; procedure prim (G: Graph; r:Node; var P:SpT);
var Q: Heap; {prioritní fronta uzlů, uspoř/Edan/E vzhledem kekey} key: Array [Node] of Real; u,v: Node; begin Q := V; {všechny uzly grafu}
for u   G   Q do key [it]  := oo; key[r]  := 0.0;     P[r]  := 0; while not isempty(Q) do
begin u := minH(Q);    Q := extractMinH(Q); for v G Successors (it) do
if member(v,Q) kk He(u, v) < keyM then begin P[i>]   := u;
Q : = removeH(t>,Q); keyM   := hE(u,v); Q := insertH(v,Q)
end
end
end
171
Korektnost Primová algoritmu
Pro důkaz korektnosti algoritmu uvažujeme tento invariant:
Pro každý uzel v je key [u] minimum z ohodnocení všech hran, kter0 spojují uzeli> s některým uzlem již vytvořen0č/Esti kostry (za minimum pr/Ezdn0 množiny považujeme oo).
Datov/E strukturaQ je prioritní fronta uzlů (může být reprezentovan/E nap. bin/Erní haldou) uspoř/Edan/E podle hodndtey.
Potom minim/Elní prvek zQ je koncový uzel hrany, kter/E m/E minim/Elní ohodnocení ze všech hran řezu oddělujícího už vytvořenou č/Est kostry od ostatních uzlů grafu. Tato hrana je tedy bezpečn/E a může být pid/Ena do budovan0 minim/Elní kostry.
Množina A hran hotov0č/Esti kostry je v Primoé algoritmu jen implicitně a je určena polem P, což je pole předchůdců každ0ho uzlu v minim/Elní košfe.
172
Složitost Primová algoritmu
Nechť n = \V\, m = \E\. Je-li prioritní fronta reprezentovan/E bin/Erní haldou, éz inicializaci prov0st včase 0(n log n).
Cyklus while proběhne n-kr/Et. To znamen/E, že všechny extrakce minim/Elních prvků z prioritní fronty potrvají celkem 0{n log n).
Cyklus for proběhne dohromady (v cel0m výpočtu) 0(m)-kr/Et. "ilo cyklu for vyžaduje čas 0(log n) a v cel0m výpočtu tedy spotřebuje čas 0(m log n). Protože v nejhorším případě bude podmínka v těle cyklu for 0(ra)-kr/Et splěna, můžeme horní odhad 0(m log n) nahradit přesným odhadem 0(m log n).
Dohromady dost/Ev/Eme složitost [n log n + n log n + m log n) — O (m log n), což je tot0ž jako u Kruskalova algoritmu.
_J