MA010 Teorie grafů Základní terminologie 1 ZÁKLADNÍ TERMINOLOGIE Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto 1.1 Definice P2(V ) označuje množinu všech nejvýše dvouprvkových neprázdných podmnožin množiny V . Nechť V je neprázdná konečná množina taková, že P2(V ) V × V = a nechť E P2(V ) V × V . Pak (V, E) nazveme prostým grafem. Pokud přitom E P2(V ), budeme mluvit o prostém neorientovaném grafu. Pokud E V × V , budeme mluvit o prostém orientovaném grafu. Prvkům množiny V říkáme uzly, prvkům množiny E říkáme hrany. Přitom prvkům množiny E P2(V ) říkáme neorientované hrany a prvkům množiny E V × V říkáme orientované hrany. O neorientované hraně {u, v} říkáme, že spojuje uzly u, v. O ori- entované hraně [u, v] říkáme, že vychází z uzlu u a vchází do uzlu v. Neorientovaná hrana se nazývá smyčka, jestliže spojuje uzel sám se sebou. Orientovaná hrana se nazývá smyčka, jestliže vchází do téhož uzlu z něhož vychází. Prostý graf bez smyček se nazývá obyčejný. Řekneme, že graf je diskrétní, jestliže E = . Označíme E(u, v) := E {{u, v}, [u, v]} V + (v) = {u V | [u, v] E} V - (v) = {u V | [v, u] E} V 0 (v) = {u V | {v, u} E} V některých aplikacích je zapotřebí, aby mezi dvěma uzly existovalo více hran. Hrany uvažujeme s jednou násobností. Formálně můžeme za E považovat zobrazení množiny P2(V ) V × V do množiny N všech nezáporných celých čísel. Mluvíme pak o grafu. Hrany, které nelze rozlišit, jsou násobné neboli paralelní. Obvykle budeme říkat graf prostému grafu. 1.2 Definice Polostupněm vstupu uzlu v v orientovaném grafu (V, E) je nezáporné celé číslo st+ (v) udávající počet hran do tohoto uzlu vcházejících, tedy st+ (v) := |{e E | (v V ).e = [v , v]}| Polostupněm výstupu uzlu v v orientovaném grafu (V, E) je nezáporné celé číslo st- (v) udávající počet hran z tohoto uzlu vycházejících, tedy st- (v) := |{e E | (v V ).e = [v, v ]}| Stupněm uzlu v v neorientovaném grafu je nezáporné celé číslo st(v) udávající počet hran spojujících tento uzel s některým uzlem zvětšený o počet smyček. Tedy st(v) = |{e E | (v V ).e = {v, v }}| + |{e E | e = {v, v}}| 1 MA010 Teorie grafů Základní terminologie 1.3 Věta 1. Pro každý neorientovaný graf (V, E) platí 2.|E| = vV st(v) 2. Pro každý orientovaný graf (V, E) platí |E| = vV st+ (v) = vV st- (v) Důkaz: Zřejmý. 1.4 Definice Jsou-li hranám grafu přiřazeny určité hodnoty, mluvíme o hranově ohodnoceném grafu. Jsou-li uzlům grafu přiřazeny určité hodnoty, mluvíme o uzlově ohodnoceném grafu. Číselně ohodnocený graf je síť. 1.5 Definice Částečný graf grafu (V, E) je každý graf (V, E ) takový, že E E. Podgraf grafu (V, E) je každý graf (V , E ) takový, že V V = a E = E (P2(V ) V × V ). Částečný podgraf grafu je každý částečný graf jeho podgrafu. Bijekce f : V1 V2 je izomorfismus grafů (V1, E1) a (V2, E2), jestliže pro každé uzly u, v V1 platí {u, v} E(u, v) {f(u), f(v)} E(f(u), f(v)) [u, v] E(u, v) [f(u), f(v)] E(f(u), f(v)) 1.6 Definice Skóre obyčejného neorientovaného grafu je neklesající posloupnost stupňů všech jeho uzlů. Skóre obyčejného neorientovaného grafu je určeno jednoznačně, ale navzájem neizo- morfní grafy mohou mít totéž skóre. Příklad:Existují čtyři navzájem neizomorfní obyčejné neorientované grafy, které mají skóre [2, 2, 2, 2, 2, 2, 2, 2, 2]. G1: G2: G3: 2 MA010 Teorie grafů Základní terminologie G4: 1.7 Věta Nechť [k1, . . . , kn] je skóre obyčejného neorientovaného grafu. Pak existuje takový oby- čejný neorientovaný graf (V, E), že V = {v1, . . . , vn}, st(vi) = ki pro každé i a {vi, vn} E n - kn i n - 1 pro všechna i. Důkaz: Mezi všemi obyčejnými neorientovanými grafy s množinoou uzlů {v1, . . . , vn} v nichž st(vi) = ki pro každé i vybereme takový, pro nějž je maximální hodnota výrazu vkV 0(vn) k Podle předpokladů alespoň jeden takový graf existuje. Připusťme, že vi V 0 (vn), vj / V 0 (vn), kde i < j < n. Pak také vn V 0 (vi) a vn / V 0 (vj), ki kj. Odtud V 0 (vj) \ V 0 (vi) = . Zvolme v V 0 (vj) \ V 0 (vi). Odstraněním hran {vi, vn},{vj, v} a přidáním hran {vi, v},{vj, vn} dostaneme obyčejný neorientovaný graf s množinou uzlů {v1, . . . , vn}, v němž st(vi) = ki pro všechna i s hod- notou vkV 0(vn) k větší o j - i. To je spor s předpokladem. 1.8 Věta Nechť [k1, . . . , kn] je neklesající posloupnost přirozených čísel. Pak [k1, . . . , kn] je skóre oby- čejného neorientovaného grafu právě tehdy, když neklesající posloupnost, kterou obdržíme přerovnáním posloupnosti [k1, . . . , kn-kn-1, kn-kn - 1, . . . , kn-1 - 1], je skóre obyčejného neorientovaného grafu. Důkaz: () Takto to plyne z předchozí věty. Stačí odebrat vn spolu s incidentními hranami z grafu (V, E). () Dostaneme přidáním uzlu kn a jeho spojením s kn posledními uzly, tj. uzly stupňů kn-kn - 1, . . . , kn - 1. Poznámka: Posloupnost [k1, . . . , kn-kn-1, kn-kn -1, . . . , kn-1-1] z věty 1.8 budeme značit S . Obecně, neklesající posloupnost, kterou obdržíme přerovnáním posloupnosti P, označíme P< . 1.9 Algoritmus Vstupní data Konečná neklesající posloupnost přirozených čísel S. Úkol Zjistit, zda S je skóre obyčejného neorientovaného grafu. Nakreslit diagram tohoto grafu. 1.krok Rekurzivně vytvoříme posloupnosti S0 := S Si+1 := (Si) < 3 MA010 Teorie grafů Základní terminologie dokud je to možné. 2.krok Pokud skončíme posloupností nul, pak S je skóre. Jinak nikoliv a algoritmus končí. 3.krok Vezmeme diskrétní graf Gmax s tolika uzly, kolik je nul v poslední posloupnosti Smax = Smax-1. 4.krok Rekurzivně vytváříme Gi-1 z Gi přidáním uzlu stupně rovného poslednímu členu v Si-1 spojeného s uzly stupňů uvedených na konci posloupnosti Si-1. Konec algoritmu. Příklad: S = [3, 3, 3, 3, 3, 5, 5] S0 = [3, 3, 3, 3, 3, 5, 5]; S0 = [3, 2, 2, 2, 2, 4] S1 = [2, 2, 2, 2, 3, 4]; S1 = [2, 1, 1, 1, 2] S2 = [1, 1, 1, 2, 2]; S2 = [1, 1, 0, 1] S3 = [0, 1, 1, 1]; S3 = [0, 1, 0] S4 = [0, 0, 1]; Tedy S není skóre. Příklad: S = [2, 3, 3, 3, 3, 3, 5] S0 = [2, 3, 3, 3, 3, 3, 5]; S0 = [2, 2, 2, 2, 2, 2] S1 = [2, 2, 2, 2, 2, 2]; S1 = [2, 2, 2, 1, 1] S2 = [1, 1, 2, 2, 2]; S2 = [1, 1, 1, 1] S3 = [1, 1, 1, 1]; S3 = [1, 1, 0] S4 = [0, 1, 1]; S4 = [0, 0] S5 = [0, 0]; Tedy S je skóre. G5 = ({a, b}, ) G4 = ({a, b, c}, {{a, b}}) G3 = ({a, b, c, d}, {{a, b}, {c, d}}) G2 = ({a, b, c, d, e}, {{a, b}, {c, d}, {c, e}, {d, e}}) G1 = ({a, b, c, d, e, f}, {{a, b}, {c, d}, {c, e}, {d, e}, {a, f}, {b, f}}) G0 = ({a, b, c, d, e, f, g}, {{a, b}, {c, d}, {c, e}, {d, e}, {a, f}, {b, f}, {a, g}, {f, g}, {b, g}, {c, g}, {d, g}}) Neorientovaný graf můžeme reprezentovat incidenční maticí. Řádky označují uzly a sloupce hrany v pevně zvoleném pořadí. Pokud daná hrana spojuje daný uzel s některým uzlem, je příslušný prvek matice roven 1, jinak 0. Orientovaný graf můžeme reprezentovat maticí sousednosti. Jak řádky, tak sloupce označují uzly v témž pevně zvoleném pořadí. Pokud z uzlu označujícího řádek vychází hrana vcházející do uzlu označujícího sloupec, pak je příslušný prvek matcie roven 1, ji- nak 0. Maticí sousednosti můžeme samozřejmě reprezentovat i neorientované grafy ­ daná matice je pak symetrická. Příklad: G: '&%$!"#u g e '&%$!"#v h /.-,()*+w '&%$!"#s '&%$!"#t f cccccccc 4 MA010 Teorie grafů Základní terminologie Incidenční matice grafu G: G e f g h s 1 0 0 0 t 0 1 0 0 u 1 1 1 0 v 0 0 1 1 w 0 0 0 1 Matice sousednosti grafu G: G s t u v w s 0 0 1 0 0 t 0 0 1 0 0 u 1 1 0 1 0 v 0 0 1 0 1 w 0 0 0 1 0 5 MA010 Teorie grafů Sledy 2 SLEDY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto Poznámka: N0 = {0, 1, . . .} Pro každé n N0 platí n = {0, . . . , n - 1}. 2.1 Definice Nechť n N0. Sledem délky n v grafu (V, E) nazveme takovou dvojici posloupností [[ei]in, [vi]in+1], že pro každé i n + 1 je vi V a pro každé i n je ei E(vi, vi+1). Jeho začátkem je uzel v0 a koncem uzel vn. Sled [[ei]in, [vi]in+1] je uzavřený, jestliže n 1 a v0 = vn. Sled [[ei]in, [vi]in+1] je tah, jestliže i = j ei = ej. Sled [[ei]in, [vi]in+1] je cesta, jestliže i = j vi = vj. Uzavřený tah [[ei]in, [vi]in+1] je kružnice, jestliže (i = 0 & i = n & i = j) vi = vj. Graf (V, E) je souvislý, jestliže pro každé jeho uzly u, v existuje pro nějaké n N0 sled [[ei]in, [vi]in+1] takový, že v0 = u a vn = v. Souvislá komponenta grafu je každý jeho maximální souvislý podgraf. Graf bez kružnic je graf, ve kterém se nevyskytuje kružnice. Příklad: neorientovaný graf G1: '&%$!"#u '&%$!"#v '&%$!"#s '&%$!"#t cccccccc orientovaný graf G2: /.-,()*+y //'&%$!"#z /.-,()*+w // OO '&%$!"#x __dddddddd příklad uzavřených sledů, které jsou tahy: s - t - u - v - t - s x y z x y z x příklady tahů, které nejsou uzavřené: s - t - u - v - t w x y z x příklady kružnic: t - u - v - t x y z x Je zřejmé, že každý uzel grafu a každá hrana neorientovaného grafu jsou obsaženy právě v jedné souvislé komponentě. 6 MA010 Teorie grafů Sledy Všimněme si, že kkružnice má začátek a směr. Každá smyčka určuje kružnici. 2.2 Definice Pokud definici 2.1 v případě orientovaného grafu pozměníme tak, že budeme požadovat ei E(vi, vi+1) E(vi+1, vi), budeme mluvit o polosledu, polotahu, polocestě, polo- kružnici a polosouvislém grafu. Příklad polosledu: // oo // // // 2.3 Definice Řekneme, že sled [[ei]in, [vi]in+1] obsahuje sled [[fi]im, [ui]im+1], jestliže existuje prosté izotonní zobrazení h : m n takové, že (i m)(fi = eh(i) & ui = vh(i) & ui+1 = vh(i)+1) 2.4 Věta Každý sled obsahuje cestu s týmž začátkem a týmž koncem, jako má on sám. Důkaz: Nechť [[ei]in, [vi]in+1] je nějaký sled a [[fi]im, [ui]im+1] je sled s týmž začátkem u0 = v0 a týmž koncem um = vm v něm obsažený, který má nejmenší možný počet hran. Kdyby pro nějaké indexy j < k platilo vj = uk, pak sled [[gi]im-k+j, [wi]im-k+j+1] definovaný vztahy gi := fi, i < j fi+k-j, j i wi := ui, i < j ui+k-j, j i by měl rovněž týž začátek a týž konec, přitom by však byl kratší. 2.5 Důsledek Graf je souvislý právě tehdy, když v něm pro každé uzly u, v existuje cesta z u do v. 2.6 Definice Uzel v neorientovaném grafu je artikulace, jestliže jeho vypuštěním včetně s ním inci- dentních hran vzroste počet souvislých komponent grafu. Hrana v neorientovaném grafu je most, jestliže jejím vypuštěním vzroste počet souvislých komponent grafu. Příklad: v následujícím grafu jsou zvýrazněny artikulace /.-,()*+ /.-,()*+ /.-,()*+ /.-,()*+ 7 MA010 Teorie grafů Sledy 2.7 Věta (1) Uzel u je artikulace právě tehdy, když existují uzly v, w od něj různé takové, že náleží do téže souvislé komponenty a každá cesta z v do w obsahuje u. (2) Hrana {u, v} je most právě tehdy, když ji obsahuje každá cesta z u do v. Jestliže je hrana mostem, jejím odstraněním vzroste počet komponent o jednu. (3) Hrana je most právě tehdy, když není obsažena v žádné kružnici. 8 MA010 Teorie grafů Eulerovské a hamiltonovské grafy 3 EULEROVSKÉ A HAMILTONOVSKÉ GRAFY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto 3.1 Definice Graf lze sestrojit jedním tahem, jestliže v něm existuje tah obsahující všechny hrany grafu. Obyčejný neorientovaný graf bez uzlů stupně 0, jehož každý uzel je sudého stupně, se nazývá eulerovský. 3.2 Věta Každý uzel eulerovského grafu je obsažen v alespoň jedné kružnici. Důkaz: Nechť u je libovolný uzel v eulerovském grafu (V, E). Podle definice není stupně 0, existuje tedy uzel v takový, že {u, v} E. Kdyby tato hrana byla mostem v grafu (V, E), jejím odstraněním ze souvislé komponenty, v níž uzly u a v leží, bychom obdrželi graf se dvěma komponentami. Každá z nich by obsahovala právě jeden uzel lichého stupně, totiž u a v. To podle věty 1.3 není možné. Podle věty 2.7 leží {u, v} na kružnici, a tedy i uzel u leží na kružnici. 3.3 Lemma Pokud lze obyčejný neorientovaný graf sestrojit jedním uzavřeným tahem a {u, v} je hrana, pak lze graf sestrojit i uzavřeným tahem začínajícím u - v - . . . Důkaz: Nechť je roven [[ei]ik, [ui]ik+1]. Pokud {u, v} = ej, pak buď u = uj a v = uj+1 nebo v = uj a u = uj+1. V prvním případě položíme rovno [[ej, ej+1, . . . , ek-1 = e0, . . . , ej-1], [u, v = uj+1, . . . , uk = u0, . . . , uj = u]], ve druhém případě [[ej, ej-1, . . . , e0 = ek-1, . . . , ej+1], [u, v = uj, . . . , u0 = uk, . . . , uj+1 = u]]. 3.4 Věta Souvislý obyčejný neorientovaný graf lze sestrojit jedním uzavřeným tahem právě tehdy, když je eulerovský. Důkaz: () Jestliže lze neorientovaný graf sestrojit jedním tahem, je souvislý, průběžné sledy spojující dvojice uzlů jsou totiž podtahy nebo tahy k nim obrácené. V uzavřeném tahu z uzlu tolikrát vycházíme, kolikrát jsme do něj vstoupili. Proto je stupeň kaž- dého uzlu sudý. Uzavřený tah má alespoň jednu hranu. () Nechť (V, E) je souvislý eulerovský graf. Podle věty 3.2 obsahuje kružnici a ta je uza- vřeným tahem. V grafu (V, E) tedy existuje uzavřený tah maximální délky, označme jej . Položme E = {{u, v} | {u, v} nepatří do tahu } a V = {u V | (v V ){u, v} E }. 9 MA010 Teorie grafů Eulerovské a hamiltonovské grafy Pokud E = , lze graf sestrojit tahem . Připusťme, že E = . Pak je (V , E ) zřejmě podgraf grafu (V, E) a přitom je eulerovský. Protože je (V, E) souvislý, exis- tuje uzel u V obsažený v tahu . Podle věty 3.2 leží uzel u na kružnici v (V , E ) ­ označme ji . Podle lemmatu 3.3 můžeme bez újmy na obecnosti předpokládat, že jak , tak začínají v u. Spojením a obdržíme uzavřený tah větší délky, než je délka . To je spor. 3.5 Věta Souvislý obyčejný neorientovaný graf lze sestrojit jedním otevřeným tahem s alespoň jed- nou hranou právě tehdy, když obsahuje právě dva uzly lichého stupně. Důkaz: () Jestliže lze graf sestrojit jedním otevřeným tahem s alespoň jednou hranou začínající v uzlu u a končící v uzlu v, pak jsou uzly u a v lichého stupně a ostatní uzly sudého stupně z podobného důvodu jako v důkazu věty 3.4. () Nechť (V, E) obsahuje právě dva uzly lichého stupně u a v. Doplňme uzel z / V a hrany {u, z}, {v, z}. Obdržíme souvislý eulerovský graf (V , E ). Podle věty 3.4 jej lze sestrojit jedním uzavřeným tahem, který podle 3.3 začíná z - u - . . . a končí . . . - v - z. Vypuštěním první a poslední hrany a prvního a posledního uzlu tahu dostaneme tah, jímž sestrojíme graf (V, E). Má alespoň jednu hranu a končí v uzlu v, který je různý od uzlu, v němž začíná, tedy u. 3.6 Definice Obyčejný neorientovaný graf se nazývá hamiltonovský, jestliže v něm existuje kružnice obsahující všechny uzly. Taková kružnice se nazývá hamiltonovská. 3.7 Věta (Diracova-Oreova) Každý obyčejný neorientovaný graf, v němž platí 3 |V | & (u, v V )({u, v} / E |V | st(u) + st(v)), je hamilotonovský. Důkaz: Připusťme, že graf (V, E) splňující výše uvedenou podmínku není hamiltonovský. Poněvadž každý graf splňující 3 |V |, v němž jsou každé dva uzly spojeny hranou, je hamiltonovský. Postupným přidáváním hran ke grafu (V, E) dostaneme graf (V , E ), který není hamiltonovský, ale přidáním další hrany {u, v} už dostaneme hamiltonovský graf. Bez újmy na obecnosti můžeme předpokládat, že (V , E ) = (V, E) a u - v - u2 - . . .-un-1 -u je hamiltonovská kružnice v grafu (V, E{u, v}). Pokud je u spojeno hranou ve (V, E) s některým uzlem ui, kde i = n - 1, pak v není spojeno hranou s ui+1, jinak by u - ui - ui+1 - . . . - u2 - v - ui+1 - . . . - un-1 - u byla hamiltonovská kružnice ve (V, E). Takových uzlů je st(u)-1, neboť u je kromě nich spojen hranou s un-1. Odtud však plyne |V |+1 st(u)+st(v)+1 = (st(u)-1)+st(v)+2 = |V \{u, v}\V 0 (v)|+|V 0 (v)|+|{u, v}| = |v|, což je ovšem spor. 10 MA010 Teorie grafů Stromy 4 STROMY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto 4.1 Definice Obyčejný neorientovaný graf bez kružnic je les. Souvislý obyčejný neorientovaný graf bez kružnic je strom. Poznámky: Protože každá smyčka určuje kružnici, je slovo obyčejný v definici zbytečné. Souvislé komponenty v lese jsou stromy. 4.2 Věta Pro souvislý obyčejný orientovaný graf (V, E) jsou tato tvrzení ekvivalentní: (i) (V, E) je strom. (ii) Každé dva uzly ve (V, E) jsou spojeny právě jednou cestou. Důkaz: () Nechť u, v V . Protože (V, E) je souvislý, alespoň jedna cesta z u do v existuje. Připusťme, že [[ei]in, [vi]in+1]] a [[fi]in, [ui]in+1]] jsou různé cesty z u do v. Nechť l je poslední index takový, že [[ei]il, [vi]il+1]] = [[fi]il, [ui]il+1]]. Označme j := min{i > l | (k)vi = vk}. Pak [[el, el+1, . . . , ej-1, fk-1, fk-2, . . . , fl], [vl, vl+1, . . . , vj = uk, uk-1, . . . , ul]] je kružnice, čímž jsme dospěli ke sporu. () Pokud by to nebyl strom, obsahoval by kružnici a v ní jsou každé dva uzly spojeny dvěma cestami. 4.3 Věta Vypuštěním jedné hrany {u, v} ze stromu dostaneme les se dvěma komponentami Cu a Cv, pro něž platí u Cu, v Cv. Důkaz: Jde o důsledek věty 2.7. Pokud by byl výsledný graf souvislý, existovala by v původním grafu kružnice. 4.4 Věta Každý strom s alespoň jednou hranou obsahuje alespoň dva uzly stupně 1. Důkaz: Nechť u, v jsou uzly spojené cestou u = v0 - v1 - . . . - vk-1 - vk = v, která má maximální délku v daném grafu. Kdyby uzel v nebyl stupně 1, existovala by hrana {v, v }, kde v = vk-1. Kdyby v = vi, existovala by kružnice vi - . . . - vk-1 - vk - vi, což je spor. Pokud v = vi, pro každé i, pak by u = v0 - v1 - . . . - vk-1 - vk = v - v byla delší cesta což je také spor. Tedy st(v) = 1 a podobně st(u) = 1. 11 MA010 Teorie grafů Stromy 4.5 Věta Nechť (V, S) je částěčný graf souvislého neorientovaného grafu (V, E). Jestliže (V, S) je les, pak existuje množina hran T taková, že S T E a (V, T) je strom. Důkaz: Nechť (V, T) je maximální graf bez kružnic obsažený ve (V, E) a obsahující (V, S). Pokud by nebyl souvislý, existovaly by uzly u a v takové, že ve (V, T) nejsou spojeny cestou. Leží tedy ve dvou různých souvislých komponentách grafu (V, T). Ve (V, E) jsou spojeny cestou. Ta obsahuje hranu, která má se souvislou komponentou obsahující uzel u společný právě jeden uzel. Jejím přidáním k T bychom obdrželi opět graf bez kružnic, což je spor. 4.6 Věta Pro souvislý neorientovaný obyčejný graf (V, E) jsou ekvivalentní tato tvrzení: (i) (V, E) je strom (ii) |V | - 1 = |E| Důkaz: Indukcí () Základní krok: Pro |E| = 0 a |E| = 1 tvrzení platí. Indukční krok: Předpokládejme, že tvrzení platí pro |E| = 1, . . . , p - 1. Dokážeme je pro |E| = p. Nechť (V, E) je strom s p hranami. Podle věty 4.4 v něm existuje uzel stupně 1. Vypusťme tento uzel s přilehlou hranou. Dostaneme strom s p - 1 hranami. Podle indukčního předpokladu platí (|V | - 1) - 1 = |E| - 1. Odtud plyne |V | - 1 = |E|. () Nechť (V, E) není strom. Podle věty 4.5 obsahuje strom (V, T). Pro něj platí podle předcházejícího |E| > |T| = |V | - 1. Je zřejmé, že každý strom s alespoň třemi uzly obsahuje uzel stupně 2. Jinak by platilo 2 = |V | - |E| + 1 vV st(v) - |E| + 1 = 2.|E| - |E| + 1 = |E| + 1 = |V | Příklad: Kolik hran má les k stromů s n uzly? |E| = |V | - k = n - k 4.7 Věta Pro obyčejný neorientovaný graf jsou ekvivalentní tato tvrzení: (i) je to strom (ii) je souvisly, ale odebráním jakékoliv hrany dostaneme nesouvislý graf Důkaz: Sporem. Nechť uzly u, v ve stromě (V, T) jsou spojeny hranou. Předpokladejme, že po jejím odebraní dostaneme souvislý graf. Pak však obsahuje cestu z u do v. Jejím doplněním o hranu {u, v} dostáváme kružnici. Spor. Nechť graf (V, E) je souvislý a odebráním kterékoliv hrany dostaneme nesouvislý graf. Kdyby to nebyl strom, obsahoval by kružnici a odebráním kterékoliv její hrany dostaneme souvislý graf, což je spor s předpokladem. 12 MA010 Teorie grafů Stromy 4.8 Definice Kořenový strom je struktura (V, E, v), kde (V, E) je strom a v V . Uzel v se nazývá kořen. Uzel x se nazývá (přímý) předchůdce uzlu y a uzel y (přímý) následník uzlu x, jestliže (jsou spojeny hranou a) x leží na cestě spojující v a y a přitom x = y. Uzly, které nemají následníky se nazývají koncové uzly neboli listy. Uspořádaný kořenový strom je struktura (V, E, v, ), kde (V, E, v) je kořenový strom a je uspořádání množiny V \ {v}, které je sjednocením lineárních uspořádání množin jednotlivých přímých následníků uzlů. Binární strom je struktura (V, E, v, f), kde (V, E, v) je kořenový strom a f je zobrazení V \{v} do množiny {pravý, levý}, jehož restrikce na množinu přímých následníků každého uzlu je prostá. 4.9 Definice Hloubka uzlu v kořenovém stromu (V, E, v) je délka cesty spojující tento uzel s kořenem. Výška kořenového stromu je délka nejdelší cesty vedoucí z kořene. 4.10 Definice Centrum, případně bicentrum, stromu (V, E) je ta neprázdná podmnožina množiny V , která zůstane po opakovaném současném odebírání všech uzlů stupně 1. 4.11 Věta Izomorfismus převádí centrum, případně bicentrum, stromu na centrum, připadně bicen- trum. Důkaz: Zřejmě konstrukce vedoucí k centru, případně bicentru, nezávisí na jménech jed- notlivých uzlů. Každému stromu můžeme přiřadit kořenový strom tak, že pokud má centrum, prohlásíme je za kořen, a pokud má bicentrum, doplníme kořen rozdělením hrany v bicentru. 4.12 Věta Stromy jsou izomorfní právě tehdy, když mají oba centrum nebo oba bicentrum a příslušné kořenové stromy jsou izomorfní. Důkaz: () Zřejmě izomorfismus je totožný s původním izomorfismem, kořen se převede na kořen, pokud jde o bicentrum () Protože se převádí kořen na kořen, je izomorfismus kořenových stromů izomorfismem stromů Uvedeme si algoritmus, který zjistí, zda dané dva uzlově ohodnocené kořenové stromy jsou izomorfní, tj. zda existuje izomorfismus, který prevede kořen na kořen a zachovává ohodnocení. 13 MA010 Teorie grafů Stromy 4.13 Algoritmus Vstupni data: Navzájem disjunktní uzlově ohodnocené kořenové stromy T1 := (V1, E1, u1) a T2 := (V2, E2, u2). Úkol: Zjistit, zda jsou izomorfní. Označení: a(v). . . ohodnocení uzlů c(v). . . číslo l(v). . . seznam čísel 1.krok: Pro oba stromy určíme počet uzlu n, výšku h a počet uzlů v každé vrstvě, tj. s touž hloubkou j. Pokud nejsou hodnoty shodné, stromy nejsou izomorfní, ZASTAV. 2.krok: Pro j = h, h - 1, . . . , 0 provádíme a) Pro každý uzel v j-té vrstvy vytvoříme seznam l(v) tak, že za ohodnocení a(v) přidáme posloupnost c(v1), . . . , c(vk), kde v1, . . . , vk jsou přímí následníci uzlu v uspořádání tak, aby tato posloupnost byla neklesající. b) Pro každý strom Ti uspořádáme uzly j-té vrstvy lexikograficky podle hodnot se- znamu l(v). Výslednou posloupnost označíme vi,1, . . . , vi,nj c) Jestliže pro nějaké p {1, . . . , nj} se seznam l(j) liší od seznamu l(v2,p), pak stromy nejsou izomorfní, ZASTAV. d) Pro uzly j-té vrstvy určíme c takto: c(vi,1) := 1 Pro l(vi,p) = l(v1,p-1) položíme c(vi,p) = c(v1,p-1) Pro l(vi,p) = l(v1,p-1) položíme c(vi,p) = c(v1,p-1) + 1 3.krok: Jestliže se algoritmus nezastavil, stromy jsou izomorfní. 4.14 Věta Algoritmus 4.13 funguje správně. Důkaz: Rovnost počtu uzlů ve stromech a uzlů v jednotlivých vrstvách stromů je nutným předpokladem existence izomorfismu. Indukcí dokážeme, že uzly v, w ležící ve sjednocení vrstev obou stromů získají tutéž hodnotu čísla c právě tehdy, když jimi určené kořenové podstromy T(v) a T(w) jsou izomorfní se zachováním ohodnocení. Základní krok: Pro poslední vrstvu tvrzení platí. Každý takový podstrom je tvořen jediným uzlem a přitom c(v) = c(w) a(v) = a(w). Indukční krok: Předpokládejme, že tvrzení platí pro všechny vrstvy s indexem vyšším než j. Rovnost c(v) = c(w) nastane právě tehdy, když l(v) = l(w). To však znamená, že a(v) = a(w) a v a w mají stejný počet přímých nasledníků s touž hodnotou čísla c. Podle indukčního předpokladu jsou podstromy určené odpovídajícími si dvojicemi přímých následníků s touž hodnotou čísla c izomorfní. Sjednocení příslušných izomorfismů podstromu sjednocené se zobrazením {v w} je izomorfismus. 14 MA010 Teorie grafů Stromy Chceme zjistit, kolik stromů existuje na dané množině uzlů. Zavedeme pomocné označení. Množinu všech stromů s množinou uzlů {v1, . . . , vn} označíme T(v1, . . . , vn). Pro T T(v1, . . . , vn) a konečnou posloupnost s = [k1, . . . , kn-2] {1, . . . , n}n-2 položíme T S : existuje [i1, . . . , in-2] {1, . . . , n}n-2 taková, že il je nejmenší prvek v množině {1, . . . , n} \ {i1, . . . , il-1, kl, . . . , kn-2}. {vil , vkl } je hrana v T pro každé l a pro {k, j} = {1, . . . , n} \ {i1, . . . , in-2} je {vk, vj} hrana v T. 4.15 Lemma Posloupnost {i1, . . . , in-2} je určena jednoznačně a pro každé l je graf T \ {vi1 , . . . , vil-1 } strom, v němž jsou uzly stupně různé od 1 právě vkl , . . . , vkn-2 . 4.16 Věta Počet stromů s danou n-prvkovou množinou uzlů je roven nn-2 . Důkaz: Definujeme zobrazení s : T(v1, . . . , vn) {1, . . . , n}n-2 a t : {1, . . . , n}n-2 T(v1, . . . , vn) taková, že T s(T), t(S) S. Je zřejmé, že odebráním uzlu stupně 1 spolu s přilehlou hranou ze stromu s alespoň třemi uzly dostaneme opět strom. Definujeme zobrazení s. Nechť T T(v1, . . . , vn). Pro l {1, . . . , n2} položíme il rovno nejmenšímu indexu uzlu stupně 1 ve stromu Te = T \ {vi, . . . , vil-1 } a kl indexu uzlu s ním sousedního. T s(T). Definujeme zobrazení t. Nechť S = [k1, . . . , kn-2] {1, . . . , n}n-2 . Pro l {1, . . . , n - 2} položíme il rovno nejmenšímu prvku v {1, . . . , n}\{i1, . . . , il-1, kl, . . . , kn}. Hranami budou {vil , vkl } a {vk, vj}, kde {k, j} = {1, . . . , n} \ {i1, . . . , in-2}. Tyto hrany jsou navzájem různé. t(S) S. Ještě bychom měli ověřit (ale neučiníme tak), že s t = id{1,...,n}n-2 a t s = idT (v1,...,vn). Příklad: Budeme hledat kód stromu. 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v8 fffffffff 76540123v5 76540123v6 ||||||||| 76540123v7 Postupně odebíráme uzly stupně 1 s nejmenším indexem a vytváříme posloupnost indexů sousedů. Nakonec tak dostáváme výsledný kód [1, 4, 4, 1, 8, 8]. Nyní výsledný kód dekódujeme. V kódu [1, 4, 4, 1, 8, 8] je 2 nejmenší index, který zde není. Vytvoříme tedy kód [2, 4, 4, 1, 8, 8]. V tomto kódu je 3 nejmenší index, který chybí. Vy- tvoříme tedy kód [2, 3, 4, 1, 8, 8]. Nyní chybí index 5, vytvoříme proto kód [2, 3, 5, 1, 8, 8]. Analogicky postupně vytvoříme kódy [2, 3, 5, 4, 8, 8],[2, 3, 5, 4, 1, 8] a [2, 3, 5, 4, 1, 6]. V po- sledním kódu se navyskytují indexy 7, 8. Pro přehlednost si kódy sepíšeme pod sebe: 15 MA010 Teorie grafů Stromy [1, 4, 4, 1, 8, 8] | [2, 4, 4, 1, 8, 8] | [2, 3, 4, 1, 8, 8] | [2, 3, 5, 1, 8, 8] | [2, 3, 5, 4, 8, 8] | [2, 3, 5, 4, 1, 8] | [2, 3, 5, 4, 1, 6] 7 | 8 Původní strom konstruujeme přidáváním hran naznačených pomocí |. "Průbežné" grafy tedy postupně vypadají takto: G1: 76540123v2 fffffffff 76540123v1 G2: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| G3: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v5 G4: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v5 G5: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v8 76540123v5 G6: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v8 76540123v5 76540123v6 ||||||||| 16 MA010 Teorie grafů Stromy A konečně výsledný strom G7: 76540123v2 fffffffff 76540123v3 76540123v1 76540123v4 ||||||||| fffffffff 76540123v8 76540123v5 76540123v6 ||||||||| 76540123v7 fffffffff 17 MA010 Teorie grafů Kostra grafu, hledání minimální kostry 5 KOSTRA GRAFU, HLEDÁNÍ MINIMÁLNÍ KOSTRY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto 5.1 Definice Kostra neorientovaného grafu je každý jeho maximální částečný graf bez kružnic. Kostra v hranově ohodnoceném grafu je minimální, jestliže má nejmenší možný součet ohodnocení hran. 5.2 Věta Každý neorientovaný graf obsahuje kostru. Kostra souvislého neorientovaného grafu je strom. Každý hranově ohodnocený neorientovaný graf obsahuje minimální kostru. Důkaz: Plyne z věty 4.5 a konečnosti grafu. Existuje několik navzájem si blízkých algoritmů umožňujících nalézt minimální kostru. 5.3 Borůvkův-Kruskalův algoritmus Vstupní data: Hranově ohodnocený souvislý neorientovaný graf G := (V, E). Úkol: Nalézt minimální kostru. Označení: H := (V, Ei) . . . posloupnost částečných podgrafů Ri . . . posloupnost rozkladů množiny V 1.krok: Hrany grafu G uspořádáme do neklesající posloupnosti podle jejich ohodnocení 2.krok: E0 := , R0 := {{v} | v V }, i := 0. 3.krok: Pro každou hranu {u, v} grafu G v pořadí daném ohodnocením provádíme: Zjistíme, zda uzly u a v patří do různých tříd rozkladu Ri. Pokud ano, provedeme i := i + 1, Ei := Ei-1 {{u, v}}, Ri := Ri-1 {[u]Ri-1 [v]Ri-1 }, tedy sjednotíme třídy rozkladu Ri-1 obsahující uzly u a v. Vlastně se ptáme, zda hrana {u, v} uzavře kružnici. 4.krok: Hi je minimální kostra. 18 MA010 Teorie grafů Kostra grafu, hledání minimální kostry 5.4 Jarníkův-Primův algoritmus Vstupní data: Hranově ohodnocený souvislý graf G := (V, E) s ohodnocením h Úkol: Nalézt minimální kostru. Označení: H := (V, Ei) . . . posloupnost částečných podgrafů 1.krok: Zvolíme libovolný uzel u V . Položíme V0 := {u}, E0 := , i := 0, M := V \ {u}. Pro každý uzel v M provedeme: Je-li {u, v} hrana grafu G, pak položíme Vv := u, dv := h({u, v}), jinak dv := . 2.krok: Jestliže M = , pak Hi je minimální kostra, ZASTAV. 3.krok: Zvolíme uzel v M, pro který je dv minimální. Položíme i := i + 1, Vi := Vi-1 {v}, Ei := Ei-1 {{Uv, v}}, M := M \ {v}. 4.krok: Pro každý uzel w M provedeme: Je-li {v, w} hrana v grafu G a její ohodnocení je menší než dw, položíme Uw := v, dw := h({v, w}). 5.krok: Jdeme na 2.krok. 19 MA010 Teorie grafů Kostra grafu, hledání minimální kostry 5.5 Obecný algoritmus Vstupní data: Hranově ohodnocený neorientovaný graf G := (V, E) Úkol: Nalézt minimální kostru. Označení: H := (V, Ei) . . . posloupnost částečných podgrafů Ri . . . posloupnost rozkladů množiny V 1.krok: Položíme i := 0, R := , R0 := {{v} | v V }. 2.krok: Jestliže R = {V }, pak Hi je minimální kostra, ZASTAV. 3.krok: Zvolíme libovolný prvek C := Ri, tedy souvislou komponentu v Hi. 4.krok: Z hran {u, v}, kde i C a v / C, vybereme hranu s minimálním ohodnocením. 5.krok: Položíme i := i + 1, Ei := Ei-1 {{u, v}}, Ri := Ri-1 \ {[u]Ri-1 , [v]Ri-1 } {[u]Ri-1 [v]Ri-1 }, tedy sjednotíme třídy rozkladu Ri-1 obsahující uzly u a v. 6.krok: Jdeme na 2.krok. 5.6 Věta Algoritmus 5.5 funguje správně. Důkaz: Protože je hran konečně mnoho, algoritmus se zastaví. Indukcí budeme dokazo- vat, že graf Hi je vždy obsažen v některé minimální kostře Ki. Základní krok: Na začátku výpočtu je graf H0 diskrétní, a proto obsažen v každé mini- mální kostře. Indukční krok: Předpokládejme, že graf Hi-1 je obsažen v minimální kostře Ki-1. Je-li přidávaná hrana {u, v}, kde u je uzel ležící ve zvolené komponentě C, hranou v Ki-1, je i Hi obsažena v Ki-1 a stačí položit Ki := Ki-1. Pokud tomu tak není, pak existuje právě jedna cesta z u do v v Ki-1. Na ní leží hrana {x, y} taková, že x C a y / C. Z volby hrany {u, v} plyne, že ohodnocení hrany {x, y} je větší nebo rovno ohodnocení hrany {u, v}. Odebráním hrany {x, y} a přidáním hrany {u, v} dostaneme z Ki-1 opět kostru Ki, jejíž ohodnocení není vyšší, a proto je také minimální. Přitom Hi je obsažen v Ki. Algoritmus skončí nalezením kostry a ta je také minimální. 5.7 Věta Všechny minimální kostry téhož souvislého neorientovaného grafu mají stejné složení ohodnocení. 20 MA010 Teorie grafů Kostra grafu, hledání minimální kostry Důkaz: Jestliže (V, T1), (V, T2) jsou minimální kostry a {u, v} T1 \ T2, pak existuje hrana {^u, ^v} T2 \ T1 taková, že {u, v} leží na cestě v T1 spojující ^u a ^v a {^u, ^v} leží na cestě v T2 spojující u, v. Když totiž vypustíme hranu {u, v} z T1, dostaneme les se dvěma souvislými komponentami Cu, Cv, přičemž u Cu a v Cv. Na cestě z u do v v T2 leží hrana {^u, ^v} spojujcící obě komponenty, přičemž ^u Cu a ^v Cv. Přitom cesta spojující u a ^u leží v Cu, cesta spojující v a ^v leží v Cv. Jejich spojením s hranou {u, v} dostaneme cestu v T1 spojující ^u a ^v. Přitom vypuštěním hrany {u, v} z T1 a přidáním {^u, ^v} dostaneme opět kostru, tedy ohodnocení {^u, ^v} je větší nebo rovno ohodnocení {u, v}. Podobně obráceně, tedy ohodnocení {u, v} je rovno ohodnocení {^u, ^v}. Nechť K, L jsou různé minimální kostry souvislého grafu G. Pak existuje konečná po- sloupnost K = K0, K1, . . . , Kp = L koster grafu G taková, že Ki-1, Ki mají stejné složení ohodnocení hran a | Ki\L | < | Ki-1\ L |. Nahrazením hrany {u, v} v Ki-1 \ L hranou {^u, ^v} v L \ Ki-1 podle předcházejícího totiž dostaneme kostru Ki s týmž složením ohodnocení hran, kde | Ki\L | = | Ki-1\L | -1. 21 MA010 Teorie grafů Souvislé komponenty 6 SOUVISLÉ KOMPONENTY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto Obvykle se používají metody založené na prohledávání grafu do hloubky. 6.1 Algoritmus hledání souvislých komponent neorientovaného grafu Vstupní data: Neorientovaný graf G := (V, E) Úkol: Nalézt souvislé komponenty. Označení: f . . . předchůdce uzlu ve stromu prohledávání v . . . referenční uzel N . . . množina nenalezených uzlů U . . . množina neprobádaných hran D . . . množina nalezených uzlů stromu prohledávání T . . . Množina nalezených hran stromu proheldávání 1.krok: Položíme N := V , U := E, D := , T := 2.krok: Je-li N = , ZASTAV. 3.krok: Zvolíme v N, položíme f(v) := 0, N := N \ {v}, D := {v} 4.krok: Jestliže neexistuje hrana vycházející z v a ležící v U, pak jestliže f(v) = 0, jdeme na 6.krok, jinak položíme v := f(v) a jdeme na 4.krok. 5.krok: Zvolíme hranu h := {v, z} U a položíme U := U \ {h}. Pokud je z N, pak provedeme N := N \ {z} D := D {z}, T := T {h}, f(z) := v, v := z a jdeme na 4.krok 6.krok: V D jsou uzly a v T hrany souvislé komponenty, položíme D := , T := a jdeme na 2.krok 22 MA010 Teorie grafů Souvislé komponenty 6.2 Algoritmus hledání souvislých komponent v orientovaných grafech Vstupní data: Orientovaný graf G := (V, E) Úkol: Nalézt souvislé komponenty v G Označení: p(v) . . . pořadí uzlu v f(v) . . . přímý předchůdce uzlu v ve stromu prohledávání r(v) . . . pomocný index D . . . množina dovolených uzlů Vývojový diagram je umístěn na následující stránce. 23 MA010 Teorie grafů Souvislé komponenty 24 MA010 Teorie grafů Souvislé komponenty Kořen komponenty je ten její uzel, který jsme objevili jako první. 6.3 Věta Algoritmus 6.2 funguje správně. Důkaz: Je zřejmé, že z komponenty K se vrátíme přes její kořen ve stromu prohledávání teprve po nalezení všech jejích uzlů. Kdyby totiž uzel u zůstal neobjeven, pak na cestě z v do u, která celá patří do K, leží hrana [v1, u1] taková, že uzel v1 byl objeven, avšak u1 ne. Z v1 jsme se však mohli vrátit až poté, co jsme nalezli u1, což je spor. Každá souvislá komponenta má tedy ve stromu prohledávání tvar T(v) \ T(v1) \ . . . \ T(vk), kde v1, . . . , vk jsou uzly, jimiž jsme z komponenty vystoupili. Stačí tedy ukázat, že algo- ritmus správně určí kořeny komponent. Indukcí dokážeme, že při návratu z uzlu v je r(v) < p(v) právě tehdy, když v není kořenem komponenty. Předpokládejme tedy, že dosud jsme při návratu všechny uzly zařadili správně. Pokud r(v) < p(v), existuje u T(v), z něhož vede šipka do w, kde p(w) < p(v) a w je dovolen. Pokud w je předchůdcem v v T, máme w v u w a tedy v a w patří do téže komponenty. Proto w není kořenem komponenty. Pokud w není předchůdcem v v T, existuje uzel z, v němž se větví cesty k w a v v T. Přitom z a w patří podle indukčního předpokladu do téže komponenty, jinak by uzel w nebyl dovolen. Dostáváme w z v u w a tedy z a v patří do téže komponenty. Proto v není kořenem komponenty. Pokud obráceně v není kořen komponenty, existují uzly této komponenty objevené před v. Z v do kořene komponenty vede cesta v = v0 v1 v2 . . . vk = u. Existuje nejmenší index l takový, že vl je uzel komponenty objevený před v. Pak ovšem r(v) r(vl-1) p(vl) < p(v). 25 MA010 Teorie grafů Hledání optimální cesty 7 HLEDÁNÍ OPTIMÁLNÍ CESTY Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto Protože algoritmy hledají nejkratší sled, graf nesmí obsahovat kružnici se záporným ohod- nocením. 7.1 Algoritmus Moorův Vstupní data: Orientovaný graf G := (V, E) uzel s V Úkol: Pro každý uzel v nalézt cestu z s do v s nejmenším počtem hran. 0.krok: Položíme (ps, ds) := (0, 0), k := 0, V0 := {s}. 1.krok: Položíme Vk+1 = . Pro každý uzel i Vk provedeme: každého neoznačeného následníka j uzlu i označíme (pj, dj) := (i, k + 1) Položíme Vk+1 := Vk+1 {j} 2.krok: Pokud Vk+1 = , ZASTAV, jinak jdi na 1.krok. 7.2 Věta Algoritmus 7.1 funguje správně. Důkaz: Máme dokázat, že po skončení platí: Pokud je uzel j označkován, pak dj := d(s, j), a pokud není označkován, pak neextistuje cesta z s do j. Zřejmě uzel dostane značku nejvýše jednou. Pokud má značku (i, k + 1), existuje cesta z s do j délky k + 1. Dostaneme ji připojením hrany [i, j] k cestě z s do i délky k, která existuje z indukčního předpokladu. Nechť d(s, j) = b. Indukcí k b dostáváme, že pak j má značku a přitom dj = b. Nechť Q je cesta z s do j délky b a nechť i je její předposlední uzel. Potom d(s, i) = b - 1 a podle indukčního předpokladu má i značku a di = b - 1. Pro k = b - 1 uzel j dostane značku dj = k + 1 = b. 7.3 Dijkstrův algoritmus Vstupní data: Nezáporně hranově ohodnocený orientovaný graf G := (V, E) Úkol: Pro každý uzel v nalézt cestu z s do v s nejmenším součtem ohodnocení hran. 26 MA010 Teorie grafů Hledání optimální cesty 0.krok: Položíme (ps, ds) := (0, 0), S := {s}, (pv, dv) := (0, ) pro v = s, pokud neexistuje hrana z s do v, (pv, dv) := (s, cs,v) pokud existuje hrana z s do v 1.krok: Pokud S = V , ZASTAV. Najdeme uzel k V \ S s nejmenší hodnotou dk. Položíme S := S {k}. Pro každý uzel j V (k) \ S provedeme: pokud dk = ck,j < dj, pak dj := dk + ck,j Jdeme na 1.krok. 7.4 Věta Algoritmus 7.3 funguje správně. Důkaz: Indukcí dokážeme, že každý uzel k je zařazen do S s dk = d(s, k), kde d(s, k) označuje délku nejkratší cesty z s do k a přitom celá tato cesta leží v S. Základní krok: Uzel s je zařazen s ds = 0 = d(s, s). Indukční krok: Předpokládejme, že dosud byl každý uzel i v S zařazen s di = d(s, i) a dk = , pak neexsituje šipka z uzlů v S do V \ S a tedy d(s, k) = pro každý uzel k V \ S. Předpokládejme dk = . Uvažujme cestu z s do k délky d(s, k), tedy nejkratší cestu, a nechť v je její první uzel ležící ve V \ S a u jeho předchůdce. Protože u byl zařazen do S, dv du + cu,v = d(s, u) + cu,v. Protože k dostal značku při zařazení jistého uzlu i do S, dk = di + ci,k = d(s, i) + ci,k je délkou jisté cesty p z s do k. Protože dk je nejmenší značka, dk dv. Odtud dostáváme dk = d(s, k), neboť dv du + cu,v = d(s, u) + cu,v d(s, k) dk dv. Proto cesta P od s po i sestává z uzlů v S podle indukčního předpokladu a po přídání k do S je celá v S. 7.5 Algoritmus Fordův Vstupní data: Hranově ohodnocený orientovaný graf G := (V, E) bez kružnic záporné délky, uzel s V . Úkol: Najít nejkratší cesty z uzlu s do ostatních uzlů. 27 MA010 Teorie grafů Hledání optimální cesty 0.krok: Položíme (as, ps, ds) := (0, 0, 0), (aj, pj, dj) := (0, 0, ) pro j = s, j V , k := 0 1.krok: Jestliže k = n - 1 nebo ai = k pro každý uzel i V , ZASTAV. Jinak pro každý uzel i V takový, že ai = k, provedeme Pro každý uzel j V - (i) provedeme Jestliže di + ci,j < dj, pak provedeme dj := di + ci,j pj := i aj := ai + 1 Položíme k := k + 1 a jdeme na 1.krok. 7.6 Věta Algoritmus 7.5 funguje správně. Důkaz: Indukcí dokážeme, že po skončení k-té iterace je dj rovno délce nejkratší cesty s nejvýše k + 1 hranami. Základní krok: Po skončení nulté iterace je ds = 0 a pro každý uzel i V - (s) platí di = cs,i, jinak di = . To jsou délky nejratších cest z uzlu s s nejvýše jednou hranou. Indukční krok: Předpokládejme, že v předchozích iteracích tvrzení platí. V k-té iteraci se délka dj nejkratší cesty z s do j s nejvýše k hranami porovnává s délkou každé cesty z s do j s k + 1 hranami, takže po jejím skončení je dj rovno délce nejkratší cesty s nejvýše k + 1 hranami. 7.7 Algoritmus vypouštění zdrojů Vstupní data: Hranově ohodnocený orientovaný graf G := (V, E) bez kružnic, uzel s V . Úkol: Najít nejkratší cesty z uzlu s do ostatních uzlů. Označení: Z. . . zásobník 28 MA010 Teorie grafů Hledání optimální cesty 0.krok: Položíme (rs, ps, ds) := (0, 0, 0), (rj, pj, dj) := (st+ (j), 0, ). Do zásobníku vložíme všechny zdroje tak, aby s byl poslední. 1.krok: Pro poslední prvek i ze Z provedeme: Odebereme i ze Z. Pro každý uzel j V - (i) provedeme: Jestliže di + ci,j < dj, pak provedeme: dj := di + ci,j pj := i rj := rj - 1 Jestliže rj = 0, přidáme j do Z. 2.krok: Jestliže Z = , ZASTAV. Jdeme na 1.krok. 7.8 Věta Algoritmus 7.8 funguje správně. Důkaz: Je zřejmé, že skončíme, neboť každý uzel se do zásobníku dostane nejvýše jednou. Z principu fundované indukce vyplývá, že se do něj dostaneme, neboť je zřejmé, že pokud se do zásobníku dostali všichni jeho předchůdci, dostal se tam také. Stačí dokázat, že pak skutečně platí dj = d(s, j) pro každý uzel j V indukcí podle pořadí, v němž jsme uzly vkládali do zásobníku. Nechť Q je cesta z s do j délky d(s, j) a i její předposlední uzel, podle indukčního před- pokladu di = d(s, i). Tedy dj di + ci,j = d(s, i) + ci,j = d(s, j). Algoritmus 7.8 můžeme použít i k nalezení nejdelších cest. Analýza kritické cesty Tato metoda se používá k analýze projektů sestávajících z činností ohodnocených délkou trvání a návazností mezi nimi. Postupujeme tak, že si nejprve sestrojíme graf projektu, v němž jsou činnosti znázorněny uzly a návaznosti mezi nimi šipkami. Tedy '&%$!"#a ///.-,()*+b znamená, že činnost b může začít teprve po skončení činnosti a. Uzly znázorňují činnosti ohodnocené délkou trvání těchto činností. Obdržíme tak orien- tovaný graf bez kružnic. /.-,()*+3 // aaaaaaaa /.-,()*+2 /.-,()*+2 @@ aaaaaaaa /.-,()*+3 /.-,()*+1 @@ Graf kreslíme tak, aby šipky směřovaly zleva doprava, myšlená časová osa probíhá také zleva doprava. Abychom mohli použít algotimus 7.8, nahradíme tento graf grafem s ohodnocenými hra- nami. Každý uzel nahradíme dvěma uzly a šipkou mezi nimi s týmž ohodnocením, jako měl původní uzel. Šipky znázorňující návaznosti budou mít nulové ohodnocení. Přitom 29 MA010 Teorie grafů Hledání optimální cesty tyto šipky vycházejí z koncových uzlů činností a vcházejí do počátečních uzlů činností. Doplníme počáteční uzel, z něhož vedou šipky do všech zdrojů, a koncový uzel do něhož vedou šipky z koncových uzlů. 0 // 2 // 0 // 0 cccccccc 3 // 0 // 0 cccccccc 2 // 0 // 1 // 0 // 3 // 0 ?? V tomto grafu hledáme nejdříve délku nejdelší cesty z počátečního uzlu do ostatních uzlů,přičemž vzdálenosti udáváme od počátku tak, aby v koncovém uzlu byla hodnota nejdelší cesty nebo předpokládaná délka trvání projektu. /.-,()*+0 0 ///.-,()*+0 2 ///.-,()*+2 0 // 0 aaaaaaaa /.-,()*+2 3 ///.-,()*+5 0 // 0 aaaaaaaa /.-,()*+5 2 ///.-,()*+7 0 ///.-,()*+8 /.-,()*+2 1 ///.-,()*+3 0 ///.-,()*+5 3 ///.-,()*+8 0 @@ Nyní dohledáme nejdelší cesty z koncového uzlu do ostatních uzlů. ?>=<89:;0|0 0 // ?>=<89:;0|0 2 // ?>=<89:;2|2 0 // 0 eeeeeeeee ?>=<89:;2|2 3 // ?>=<89:;5|5 0 // 0 eeeeeeeee ?>=<89:;5|6 2 // ?>=<89:;7|8 0 // ?>=<89:;8|8 ?>=<89:;2|4 1 // ?>=<89:;3|5 0 // ?>=<89:;5|5 3 // ?>=<89:;8|8 0 >>}}}}}}}}} Nejdelší cesty jsou kritické. Na nich ve skutečnosti závisí doba trvání projektu. Kritická cesta je tvořena uzly s ohodnocením x|x. 30 MA010 Teorie grafů Hledání optimální cesty t (0) i . . . nejdříve možný začátek činnosti [i, j] t (1) i . . . nejpozději přípustný konec činnosti [i, j] 31 MA010 Teorie grafů Hledání optimální cesty t (0) j . . . nejdříve možný konec činnosti [i, j] t (1) j . . . nejpozději přípustný konec činnosti [i, j] yi,j. . . doba trvání činnosti [i, j] Rezervy činnosti [i, j] Celková rezerva (CR): CRi,j = t (1) j - t (0) i - yi,j = t (1) i - t (0) i = t (1) j - t (0) j Volná rezerva (RV): RVi,j = t (1) j - t (0) i - yi,j = t () j - t (0) j Udává, o kolik lze posunout začátek činnosti, aby se nezměnily nejdříve možné začátky všech činností bezprostředně následu- jících. Závislá rezerva (RZ): RZi,j = t (1) j - t () i - yi,j = t (1) i - t () i Udává, o kolik lze prodloužit trvání činnosti, aby se nezměnil nejpozději přípustný konec činností bezprostředně předcházejí- cích. Nezávislá rezerva (RN): RNi,j = t () j - t () i - yi,j Udává, o kolik lže prodloužit trvání činnosti, aby se nezměnil nejdříve možný začátek činností bezprostředně následujících a nejpozději přípustný konec činností bezprostředně předcházejí- cích. Propustnost cesty v hranově ohodnoceném orientovaném grafu je minimum z ohodno- cení jejích hran. 7.9 Algoritmus nalezení cesty s největší propustností Vstupní data: Hranově ohodnocený orientovaný graf G := (V, E), uzel s V . Úkol: Najít cesty s největší propustností z uzlu s do ostatních uzlů. Označení: bj. . . dosud nalezená největší propustnost cesty z s do j ci,j. . . ohodnocení hrany [i, j] 1.krok: Položíme (ps, bs) := (0, ), ostatní uzly bez značky, S := {s}, v := s. 2.krok: Pro všechny uzly u V - (v) provedeme: Pokud bu < min{bv, cv,u}, pak provedeme bu := min{bv, cv,u} Pokud S = V , ZASTAV. Najdeme uzel v S s maximálním bv, položíme S := {v}, jdeme na 2.krok. 32 MA010 Teorie grafů Toky v sítích 8 TOKY V SÍTÍCH Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto Je dán orientovaný graf G := (V, E) s nezáporným ohodnocením hran, jemuž říkáme ka- pacita, počáteční uzel uzel s a koncový uzel t. '&%$!"#i ///.-,()*+j bi,j. . . kapacita hrany [i,j] xi,j. . . tok hranou [i,j] Hledáme nezáporné ohodnocení xi,j takové, že 0 xi,j bi,j a jV +(i) xj,i - jV -(i) xi,j = 0, i V \ {s, t}. Takovému ohodnocení říkáme tok. Číslo f(x) := jV +(t) xj,t - jV -(t) xt,j je velikost toku z s do t. Budeme hledat tok s maximální velikostí. Takový tok je maximální. Nechť P je polocesta v G. Množinu souhlasně orientovaných hran označíme P + , množinu nesouhlasně orientovaných hran P - . Souhlasně orientované hraně [i, j] přiřadíme bi,j - xi,j, nesouhlasně orientované hraně [i, j] přiřadíme xi,j, kterým říkáme rezervy. Nejmenší z rezerv hran polocesty je rezerva polocesty. Zlepšující polocesta je polocesta z s do t s kladnou rezervou. Podmnožina S V je řez mezi s a t, jestliže s S, t / S (zjednodušené, obvykle se za řez bere množina hran). Součet kapacit hran vycházejících z uzlů v S a vcházejících do uzlů ve V \ S je kapacita řezu. Značíme b(S, V \ S). Platí f(x) = x(S, V \ S) - x(V \ S, S) b(S, V \ S) Minimální řez je řez s minimální kapacitou. 8.1 Věta Velikost maximálního toku z s do t je rovna kapacitě minimálního řezu mezi s a t. Důkaz: Maximální tok existuje, neboť jde o maximum spojité funkce na kompaktní mno- žině (=ohraničená a uzavřená). Minimální řez existuje, protože řezů je konečně mnoho. Označme x maximální tok z s do t a b hodnotu minimálního řezu mezi s a t. Zřejmě f(x ) = b(S, V \ S). Nechť S je množina všech těch uzlů, do nichž vede z s polocesta s kladnou rezervou a která navíc obsahuje s. Pokud by t S, existovala by zlepšující polocesta z s do t a tok bychom mohli zvětšit o rezervu této polocesty, což je spor. Tedy t / S, a S je řez mezi s a t. Pro každou hranu [i, j] vedoucí z S do V \ S platí, že xi,j = bi,j, jinak by uzel j patřil do S a pro každou hranu [i, j] vedoucí z V \ S do S platí xi,j = 0, jinak by uzel i patřil do S. Tedy f(x ) = x (S, V \S)-x (V \S, S) = x (S, V \S) = b(S, V \S). 33 MA010 Teorie grafů Toky v sítích 8.2 Věta Tok x z s do t je maximální právě tehdy, když neexistuje zlepšující polocesta z s do t. Důkaz: () Pomocí zlepšující polocesty by se dal tok zvětšit. () Položíme S := {v | existuje polocesta z s do v s kladnou rezervou}. Pak f(x) = b(S, V \ S), takže x je maximální tok a S je minimální řez. 8.3 Fordův-Fulkersonův algoritmus 1.krok: Položíme xij = 0 pro každou hranu [i, j]. 2.krok: Moorovým algoritmem nalezneme zlepšující polocestu z s do t s nejmenším počtem hran. Pokud neexistuje, pak ZASTAV. 2.krok: Zvětšíme tok o rezervu nelené zlepšující polocesty. Jdeme na 2.krok. 8.4 Věta Algoritmus 8.3 funguje správně. Důkaz: Pokud výpočet skončí, neexistuje zlepšující polocesta, a tedy tok je maximální. Dokážeme, že výpočet skončí po konečně mnoha krocích. Označíme (k) (i) délku nejkratší zlepšující polocesty z s do i po k zlepšeních, to jest pro tok x( k). Dále označíme (k) (i) délku nejkratší zlepšující polocesty s (kladnou rezervou) z i do t po k zlepšeních, to jest pro tok x(k) . Nejdříve ukážeme, že pro každé k a každý uzel i platí (k) (i) (k+1) (i) & (k) (i) (k+1) (i). Sporem dokážeme první nerovnost. Připusťme, že pro jisté k a jistý uzel i platí (k+1) (i) < (k) (i). Bez újmy na obecnosti můžeme předpokládat, že pro každý uzel j platí (k+1) (i) (k+1) (j) nebo (k) (j) (k+1) (j). Nechť j je předposlední uzel na nejkratší zlepšující polocestě Q z s do i pro tok x(k+1) . Pak (k+1) (i) = (k+1) (j) + 1, a tedy (k) (j) + 1 (k+1) (i). Nechť tok x(k) byl zlepšen po zlepšující polocestě P z s do t. Pokud hrana [i, j] nepatřila do P nebo byla v P nesouhlasná, pak 0 < x (k+1) ij x (k) ij . Proto (k) (i) (k) (j)+1 (k+1) (i), což je spor s předpokladem. Pokud hrana [j, i] nepatřila do P nebo byla souhlasná v P, pak x (k) ji x (k+1) ji < bji. Proto (k) (i) (k) (j) + 1 (k+1) (i), což je spor s předpokladem. Pokud hrana [j, i] byla nesouhlasná v P, pak (k) (j) = (k) (i) + 1, a tedy (k) (i) + 2 (k+1) (i), což je spor s předpokladem. Pro je důkaz obdobný. Řekneme, že souhlasná hrana je kritická, jestliže x (k+1) ij = bij, a že nesouhlasná hrana je kritická, jestliže x (k+1) ij = 0. 8.5 Věta Na každé zlepšující polocestě existuje kritická hrana. Důkaz: Nechť [i, j] je kritická hrana v (k + 1)-ní zlepšující polocestě P. Délka m(P) = (k) (i) + (k) (i) = (k) (j) + (k) (j). 34 MA010 Teorie grafů Toky v sítích Pokud [i, j] je i v (r + 1)-ní zlepšující polocestě a r je nejmenší takové, že k r, je v ní opačně. Pokud tedy (k) (i) = (k) (j) + 1, pak (r) (i) = (r) (j) + 1. Odtud m(P) + 2 = (k) (j) + (k) (j) + 2 (r) (j) + (k) (i) + 1 = (r) (i) + (k) (i) (r) (i) + (r) (i) = m(Q). Protože každá polocesta má nejvýše n - 1 hran, může být každá hrana kritická nejvýše n 2 -krát. Můžeme tedy provést nejvýše m.n 2 zlepšení. 35 MA010 Teorie grafů Párování 9 Párování Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto 9.1 Definice Neorientovaný graf je bipartitní, jestliže jeho množinu uzlů lze rozdělit na dvě disjunktní podmnožiny tak, že každá hrana má jeden uzel v jedné a druhý v druhé. 9.2 Definice Párování v neorientovaném grafu je každý jeho částečný podgraf, v němž má každý uzel stupeň nejvýše 1. Párování je maximální, jestliže má největší možný počet hran. Bipartitnímu grafu můžeme přiřadit orientovaný graf tak, že hrany budou vycházet z uzlu v první množině a vcházet do uzlu ve druhé množině. Můžeme přidat počáteční uzel a hrany vycházející z tohoto uzlu a vcházející do všech uzlů první množiny a koncový uzel a hrany vycházející ze všech uzlů druhé množiny a vcházející do koncového uzlu. Hrany ohodnotíme vhodně číslem 1. 9.3 Lemma Existuje vzájemná jednoznačná korespondence (bijekce) mezi celočíselnými toky z s do t v přiřazeném orientovaném grafu a párováním v původním grafu. Je určena tak, že pro tok x {{a, b}|xab = 1} je párování a pro párování H je xsv = 1, jestliže z v vychází hrana párování H xvu = 1, jestliže [v, u] je hrana párování H xut = 1, jestliže z u vychází hrana párování H celočíselný tok z s do t. Velikost toku je rovna počtu hran párování. V bipartitním grafu tedy nalezneme maximální párování tak, že k němu sestrojíme pří- slušný ohodnocený orientovaný graf a najdeme v něm maximální tok. Hrany, v nichž je hodnota toku 1, tvoří maximální párování. 9.4 Definice Uzel je volný vzhledem k danému párování, jestliže nesousedí se žádnou hranou párování. Cesta je střídavá, jestliže se v ní střídají hrany patřící a nepatřící do párování. Je volná, jestliže začíná ve volném uzlu a končí ve volném uzlu. 9.5 Bergerova věta Párování je maximální právě tehdy, když k němu neexistuje volná střídavá cesta. Důkaz: () Kdyby existovala, pak výměnou hran patřících do této cesty dostaneme páro- vání s větším počtem hran () Nechť X je Párování, ke kterému neexistuje volná střídavá cesta. Nechť X je nějaké maximální párování. Položme H = X X . (V, H) má uzly stupně 1,2, a proto jeho souvislé komponenty jsou některých z těchto typů: jedna hrana, cesta sudé délky nebo kružnice sudé délky. Počet hran párování X je tedy týž, jako počet hran maximálního párování X . 36 MA010 Teorie grafů Párování 9.6 Algoritmus Edmondsův Vstupní data: Neorientovaný graf (V, E) a párování X Úkol: Najít volnou střídavou cestu. Označení: S : L : . . . značky (sudá, lichá) 1.krok: Jestliže neexistuje volný uzel, pak ZASTAV. 2.krok: Všechny volné uzly dostanou značku S : 0 Pokud bu < min{bv, cv,u}, pak provedeme bu := min{bv, cv,u} Pokud S = V , ZASTAV. Najdeme uzel v S s maximálním bv, položíme S := {v}, jdeme na 2.krok. 3.krok: Označkovaný ale neprozkoumaný uzel i prozkoumáme takto: Pokud i má značku S, pak každý neoznačkovaný uzel j takový, že {i, j} E \ X, dostane značku L : i. Jestliže i má značku L a {i, j} E \ X a j je neoznačkovaný, pak j dostává značku S : i. 9.7 Věta Nechť Z je květ objevený v grafu G při značkování vzhledem k X. Nechť po kontrakci květu Z na uzel Z vznikne z G graf G a z X párování X . Potom v G existuje volná střídavá cesta vzhledem k X právě tehdy, když v G existuje volná střídavá cesta pro X. Důkaz: () Volnou střídavou cestu v G vzhledem k X doplníme úsekem v květu podle druhu hran. () Tento směr je složitý. 37 MA010 Teorie grafů Míry souvislosti grafu 10 Míry souvislosti grafu Podle přednášky Doc. RNDr. Josefa Niederleho, CSc. zpracoval Ondřej Bitto V této kapitole budeme zkoumat neorientované grafy. Nechť G := (V, E) je souvislý. Míru souvislosti můžeme udat pomocí hranových a uzlových řezů. 10.1 Definice Uzlový řez je podmnožina A V taková, že (V \ A, {e E|e A = }) je nesouvislý. Hranový řez je podmnožina A E taková, že (V, E \ A) je nesouvislý. Každý netriviální souvislý graf má hranový řez. Každý neúplný souvislý graf má uzlový řez. 10.2 Definice Minimální velikost uzlového řezu se nazývá uzlová souvislost grafu a značí (G). Pro úplný graf (Kn) := n - 1. Minimální velikost hranového řezu se nazývá hranová souvislost grafu a značí (G). Triviální graf K1 má hranovou souvislost (K1) := 0. Každý nesouvislý graf G má (G) := 0 a (G) := 0. Cesty z u do v jsou vnitřně disjunktní, jestliže nemají společný vnitřní uzel. Cesty z u do v jsou hranově disjunktní, jestliže nemají společnou hranu. 38