MA2BP_PDM1 Diskrétní matematika 1 3. Stromy, hledání minimální kostry, nej kratší cesta Lukáš Másilko Středisko pro pomoc studentům se specifickými nároky Masarykova univerzita 17. 10. 2017 17. 10. 2017 1/37 Program prezentace H Vlastnosti stromů B Kostra grafu B Algoritmy pro nalezení minimálni kostry ■ Kruskalův algoritmus ■ Borůvkův algoritmus ■ Jarníkův algoritmus □ Hledání nej kratší cesty ■ Dijkstrův algoritmus H Použité zdroje 17. 10. 2017 2 / 37 Základní pojmy Definice 4.1, 4.2, 4.3 (MILKOVA): □ Les je graf, který neobsahuje kružnici. Q Strom je souvislý graf, který neobsahuje kružnici. B Buď T = {V, E) strom. Vrchol u G V stupně 1 nazývame listem, vrchol v E V stupně většího než 1 nazývam vnitřním vrcholem stromu T. j Poznámka: ■ Strom obsahující pouze jeden vrchol nazývame triviálním stromem. ■ Každá komponenta lesa je strom. 17. 10. 2017 3 / 37 Ukázka stromu 17. 10. 2017 4 / 37 Charakteristika stromů Věta 4.1 (MILKOVA): Pro každý graf G = {V,E) jsou následující podmínky ekvivalentní: H Graf G je strom. B Pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y. B Graf G je souvislý a každá jeho hrana je most. □ Graf G je souvislý a platí vztah \ V\ — \E\ + 1. B Graf G neobsahuje kružnici a každý graf vzniklý z grafu G přidáním hrany, která spojuje libovolné dva vrcholy grafu G, které nejsou sousední, již kružnici obsahuje. 17. 10. 2017 5 / 37 Kostra grafu Definice 4.8 (MILKOVA): Libovolný strom T = (V, E1), který je podgrafem grafu G — (\/, E), nazýváme kostra grafu G. Příklad kostry: viz barevně vyznačený podgraf na následujícím obrázku. 17. 10. 2017 6 / 37 Souvislost grafu a kostra Věta 4.2 (MILKOVA): Pro každý graf G = (V,E) platí: Graf G je souvislý právě tehdy, když obsahuje alespoň jednu kostru. Důkaz: Tvrzení je ve tvaru ekvivalence, je tedy třeba dokázat oba směry implikace. O G je souvislý =4> G obsahuje alespoň jednu kostru. B G obsahuje alespoň jednu kostru =4> G je souvislý. 17. 10. 2017 7 / 37 Souvislost grafu a kostra Věta 4.2 (MILKOVA): Pro každý graf G = (V,E) platí: Graf G je souvislý právě tehdy, když obsahuje alespoň jednu kostru. Důkaz: Tvrzení je ve tvaru ekvivalence, je tedy třeba dokázat oba směry implikace. D G je souvislý =4> G obsahuje alespoň jednu kostru. B G obsahuje alespoň jednu kostru =4> G je souvislý. Proveďme důkaz obou implikací: "<^:" Předpokládejme, že graf G obsahuje alespoň jednu kostru. 17. 10. 2017 7 / 37 Souvislost grafu a kostra Věta 4.2 (MILKOVA): Pro každý graf G = (V,E) platí: I Graf G je souvislý právě tehdy, když obsahuje alespoň jednu kostru. I Důkaz: Tvrzení je ve tvaru ekvivalence, je tedy třeba dokázat oba směry implikace. O G je souvislý =4> G obsahuje alespoň jednu kostru. B G obsahuje alespoň jednu kostru =4> G je souvislý. Proveďme důkaz obou implikací: "<^:" Předpokládejme, že graf G obsahuje alespoň jednu kostru. ■ Dle Definice 4.8 je kostra K = {V, E') podgrafem obsahujícím všechny vrcholy původního grafu G. ■ 17. 10. 2017 7 / 37 Souvislost grafu a kostra Věta 4.2 (MILKOVA): Pro každý graf G = (V,E) platí: I Graf G je souvislý právě tehdy, když obsahuje alespoň jednu kostru. I Důkaz: Tvrzení je ve tvaru ekvivalence, je tedy třeba dokázat oba směry implikace. O G je souvislý =4> G obsahuje alespoň jednu kostru. B G obsahuje alespoň jednu kostru =4> G je souvislý. Proveďme důkaz obou implikací: "<^:" Předpokládejme, že graf G obsahuje alespoň jednu kostru. ■ Dle Definice 4.8 je kostra K = {V, E') podgrafem obsahujícím všechny vrcholy původního grafu G. ■ Navíc je K stromem, tudíž K je souvislý (dle definice stromu). 17. 10. 2017 7 / 37 Souvislost grafu a kostra Věta 4.2 (MILKOVA): Pro každý graf G = (V,E) platí: I Graf G je souvislý právě tehdy, když obsahuje alespoň jednu kostru. I Důkaz: Tvrzení je ve tvaru ekvivalence, je tedy třeba dokázat oba směry implikace. O G je souvislý =4> G obsahuje alespoň jednu kostru. B G obsahuje alespoň jednu kostru =4> G je souvislý. Proveďme důkaz obou implikací: "<^:" Předpokládejme, že graf G obsahuje alespoň jednu kostru. ■ Dle Definice 4.8 je kostra K = {V, E') podgrafem obsahujícím všechny vrcholy původního grafu G. ■ Navíc je K stromem, tudíž K je souvislý (dle definice stromu). Závěr: Samotný graf G je tedy souvislý. 17. 10. 2017 7 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. 2 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. 2 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: necht tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. 2 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: necht tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. ■ Indukční krok: Uvažujme souvislý graf G' o m + 1 hranách. 2 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: necht tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. ■ Indukční krok: Uvažujme souvislý graf G' o m + 1 hranách. O G' neobsahuje kružnici G' je strom a jeho kostrou je G' samotný. 2 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: necht tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. ■ Indukční krok: Uvažujme souvislý graf G' o m + 1 hranách. O G' neobsahuje kružnici G' je strom a jeho kostrou je G' samotný. B G' obsahuje kružnici C odebráním libovolné hrany e G C dostávame opět souvislý graf G' — e, který už má pouze m hran 17. 10. 2017 8 / 37 Pokračovaní důkazu Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviálni strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: necht tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. ■ Indukční krok: Uvažujme souvislý graf G' o m + 1 hranách. Q G' neobsahuje kružnici G' je strom a jeho kostrou je G' samotný. B G' obsahuje kružnici C odebráním libovolné hrany e G C dostávame opět souvislý graf G' — e, který už má pouze m hran ^> dle indukčního předpokladu a tvrzení (*) obsahuje graf G' — e alespoň jednu kostru. Ta je zároveň i kostrou grafu G'. 17. 10. 2017 8 / 37 Pokračovaní důkazu 11 :" Předpokládejme, že graf G je souvislý. Důkaz faktu, že obsahuje alespoň jednu kostru, provedeme matematickou indukcí vzhledem k počtu hran m > 0. ■ Báze: m = 0, souvislý graf G má 0 hran =4> jde o triviální strom s jedním izolovaným vrcholem. Kostrou grafu G je graf G samotný. ■ Indukční předpoklad: nechť tvrzení platí pro souvislý graf G s m hranami, tj. (*) souvislý graf G o m hranách obsahuje alespoň jednu kostru. ■ Indukční krok: Uvažujme souvislý graf G' o m + 1 hranách. Q G' neobsahuje kružnici G' je strom a jeho kostrou je G' samotný. B G' obsahuje kružnici C odebráním libovolné hrany e £ C dostáváme opět souvislý graf G' — e, který už má pouze m hran ^> dle indukčního předpokladu a tvrzení (*) obsahuje graf G! — e alespoň jednu kostru. Ta je zároveň i kostrou grafu G'. Závěr: Graf G tedy obsahuje alespoň jednu kostru. a ►<»►<» ► = 17. 10. 2017 8 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V, E) platí vztah £1 > \ V\ - 1. Důkaz: 17. 10. 2017 9 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V,E) platí vztah E\> V - 1. ™^^^^— Důkaz: Souvislý graf obsahuje alespoň jednu kostru K = (V, £'), kde E' C E (dle Věty 4.2). 17. 10. 2017 9 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V, E) platí vztah E > V -1. Důkaz: Souvislý graf obsahuje alespoň jednu kostru K = (V, E'), kde £'C£ (dle Věty 4.2). Pro kostru K platí \E' V - 1 17. 10. 2017 9 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V, E) platí vztah E > V -1. Důkaz: Souvislý graf obsahuje alespoň jednu kostru K = (V, E'), kde £'C£ (dle Věty 4.2). Pro kostru K platí \E' platí\E\ > \ V\ - 1. V - 1. Protože E' C E, 17. 10. 2017 9 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V, E) platí vztah EI > \v\ -1- Důkaz: Souvislý graf obsahuje alespoň jednu kostru K = (V, E'), kde £'C£ (dle Věty 4.2). Pro kostru K platí \E'\ = | V\ - 1. Protože E' C E, platí |E| > IVI - 1. Příklad: Je dáno skóre (1,1,1,1,2,2,2) grafu G. Může být graf G souvislý? 17. 10. 2017 9 / 37 Podmínka pro souvislý graf Důsledek 4.1 (MILKOVA): V souvislém grafu G = (V,E) platí vztah E\ > \ V\ - 1. Důkaz: Souvislý graf obsahuje alespoň jednu kostru K = (V, E1), kde E' C E (dle Věty 4.2). Pro kostru K platí \Eř platí \E\ >\V\-1. V -1. Protože E' C E, Příklad: Je dáno skóre (1,1,1,1, 2, 2, 2) grafu G. Může být graf G souvislý? Řešení: Počet vrcholů |\/| = 7. Počet hran spočítáme: E\ = (1 + 1 + 1 + 1 + 2 + 2 + 2)/2 = 5. Ověříme podmínku pro souvislý graf \E\ > \ V\ — 1 z Věty 4.1. Není pravda, že 5 > 7 — 1. Proto graf se zadaným skóre nemůže být souvislý. 17. 10. 2017 9 / 37 Počet koster v souvislém grafu Platí zrejme následující úvahy: H Obsahuje-li souvislý graf právě jednu kružnici délky k, pak obsahuje k koster. B Obsahuje-li souvislý graf p po dvou hranově disjunktních kružnic Ci, C2,..., Cp, jejichž délky jsou postupně /ci, /c2,..., kp, pak obsahuje k± • /c2...../cp koster. B Obsahuje-li graf G právě jednu kostru, pak je graf G stromem. Věta 4.3 (Arthur Cayley): Počet koster úplného grafu Km n > 2, je nn~2. 17. 10. 2017 10 / 37 Příklad 1 17. 10. 2017 11 / 37 Příklad 1 Řešení: V grafu je pouze jedna kružnice délky 5. Proto je počet koster roven 5. 17. 10. 2017 11 / 37 Příklad 2 17. 10. 2017 12 / 37 Příklad 2 Řešení: V grafu jsou dvě po hranách disjunktní kružnice, jedna délky 3, druhá délky 5. Proto je počet koster roven 5 • 3 = 15. 17. 10. 2017 12 / 37 Příklad 3 17. 10. 2017 13 / 37 Příklad 3 Řešení: V grafu jsou vidět dva zajímavé podgrafy: úplný graf K4 a kružnice délky 5. Víme, že pro úplný graf K4 platí, že počet koster je 42 = 16. Obsahuje-li graf navíc ještě kružnici délky 5, pak je počet koster celého grafu roven 16 • 5 = 80. 17. 10. 2017 13 / 37 Příklad 4 Řešení: Graf je stromem, počet koster je tedy roven 1. Prohrnování silnic V království je 6 měst - označme je A, B, C, D, E, F, a některá z nich jsou spojena přímou silnicí. Křižovatky jsou pouze ve městech. Mezi některými městy přímá silnice nevede, ale z každého města se dá po silnicích dostat do libovolného jiného. V noci se přihnala se vánice a zasněžila všechny silnice v celém království. Napadlo až metr sněhu. Odhrabovačů je málo a takovou sněhovou nadílku budou odklízet ještě hodně dlouho. Rozhodněte, které silnice se mají odhrabat jako první, aby mezi každýma dvěma městy vedla sjízdná silnice. Přikládáme plán království s délkou jednotlivých cest. 17. 10. 2017 15 / 37 Problém minimální kostry Mějme ohodnocený souvislý graf G — {V^ E). Každé hraně e G E je dáno reálné číslo i/i/(e), tzv. ohodnocení hrany. Mezi všemi kostrami grafu G najděte kostru H = {V, E') takovou, že součet ohodnocení jejích hran w(H) — J^eeE' w{e) nabývá minimální hodnoty. Kostru H nazveme minimální kostrou grafu G a w(H) cenou kostry H. Poznámky: □ Minimálních koster může být více. B V praxi se setkáváme většinou s tím, že ohodnocení hran je nezáporné. B Čeští matematici stáli u zrodu nejznámějších algoritmů pro nalezení minimální kostry. Prvním byl ve 20. letech 20. století brněnský matematik Otakar Borůvka (elektrifikace na jižní a západní Moravě). 17. 10. 2017 16 / 37 Kruskalův algoritmus Věta 4.18 (FUCHS): Buď (V, E, w) konečný souvislý graf s ohodnocením hran w. Všechny hrany ei,..., en G E sestavme do posloupnosti tak, aby w{e{) < w^ez) < • • • < w(en). Algoritmus pro nalezení minimální kostry grafu G je následující: (1) Polož E0 = 0, /' = 1. (2) Obsahuje graf (V, E,_iU{e,}) kružnici? ANO: krok (4). NE: krok (3). (3) Polož E-, = E/_i U {e/}. Jdi na krok (5). (4) Polož E; = E/_i. (5) Je / = nl ANO: Jdi na krok (6). NE: Jdi na krok (8). (6) Polož E-, = K. (7) KONEC. (U, K) je minimální kostra. (8) Zvětši hodnotu / o jedničku a jdi na krok (2). 17. 10. 2017 17 / 37 Příklad použití Kruskalova algoritmu Počátek algoritmu - neorientovaný graf o sedmi uzlech A, B, C, D, E, F, G A 7 B 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: C-2-F (patří do kostry) F 7 G /;A ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ 5 \ 6 .•*' 5 / 6 ♦ ♦ ♦ ♦ ♦ ♦ A 7 B 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: D-2-E (patří do kostry) 5 \ 6 / 5 /6 A B □ g ► < -E ► < = 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: C-3-D (patří do kostry) F 7 G A 7 B Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: D-3-G (patří do kostry) F 7 G A 7 B Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: D-4-F (nepatří do kostry) 5 \ 6/ *. 5 / 6 ♦ ♦ A B 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: D-4-F (přidáním hrany D-4-F by vznikla kružnice CDFC) 5 \ 6/ 5 /6 A B □ g ► < -E ► < = 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: E-4-G (nepatří do kostry) 5 \ 6/ *. 5 / 6 A B □ g ► < -E ► < = 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: E-4-G (přidáním hrany E-4-G by vznikla kružnice DEGD) 5 \ 6/ 5 /6 A B 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu 17. 10. 2017 18 / 37 Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: B-5-D (patří do kostry) F 7 G C Příklad použití Kruskalova algoritmu Aktuálně zpracovávaná hrana: A-5-C (patří do kostry) F 7 G A 7 B Příklad použití Kruskalova algoritmu Konec algoritmu, kostra je úplná A 7 B 17. 10. 2017 18 / 37 Příklad použití Borůvková algoritmu Počátek algoritmu - neorientovaný graf o sedmi uzlech (stromech) A, B, C, D, E, F, G A 7 B 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {A}: nejkratší hrana A-5-C ke stromu {C} =4> nový strom {A, C} 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {B}: nejkratší hrana B-5-D ke stromu {D} =4> nový strom {B, D} ♦ ♦ ♦ ♦ ♦ ♦ 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {E}: nejkratší hrana E-2-D ke stromu {B, D} => nový strom {B, D, E} 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {F}: nejkratší hrana F-2-C ke stromu {A, C} =4> nový strom {A, C, F} F 7 G 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {G}: nejkratší hrana G-3-D ke stromu {B, D, E} => nový strom {B, D, E, G} 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Sumarizace: dva stromy, modrý: {A, C, F}, červený: {B, D, E, G} F 7 G 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Aktuálně zpracovávaný "strom" {A, C, F}: nejkratší hrana C-3-D ke stromu {B, D, E, F} 17. 10. 2017 19 / 37 Příklad použití Borůvková algoritmu Konec algoritmu - spojení posledních dvou stromů =>- minimální kostra. A 7 B 17. 10. 2017 19 / 37 Příklad použití Jarníkova algoritmu Počátek algoritmu - neorientovaný graf G o vrcholech A, B, C, D, E, F, G a vyznačeným stromem S = {A} F 7 G .................• ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ D/ 3 *• • 2 C#.......■.......#.......■.......»E ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ♦ * ♦ ♦ ♦ 5\ 6/ 5 /6 ♦ * ♦ ♦ ♦ ♦ A 7 B 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A}\ nejkratší hrana od S do G — S je hrana A-5-C =4> nový strom S = {/4, C} A 7 B 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A, C}: nejkratší hrana od S do G — S je hrana C-2-F =4> nový strom S = {/4, C, F} 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A, C, F}: nejkratší hrana od S do G — S je hrana C-3-D =4> nový strom S = {/4, C, D, F} F 7 G 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A, C, D, F}: nejkratší hrana od S do G — S je hrana D-2-E =4> nový strom S = {/4, C, D, E, F} 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A, C, D, E, F}: nejkratŠT hrana od S do G - S je hrana D-3-G nový strom S = {A, C, D, E, F, G} F 7 G 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Aktuálně zpracovávaný "strom" S = {A, C, D, E, F, G}: nejkratší hrana od S do G - S je hrana D-5-B =4> nový strom S = {A, B, C, D, E, F, G} f 7 9 17. 10. 2017 20 / 37 Příklad použití Jarníkova algoritmu Konec algoritmu, ve stromu S jsou všechny vrcholy původního grafu G A 7 B 17. 10. 2017 20 / 37 Srovnání algoritmů □ Kruskalův algoritmus nejprve uspořádá hrany podle ohodnocení, pak je prochází a když aktuální hrana nevytváří kružnici, přidá ji do minimální kostry. Pro grafy s menším počtem hran je nejefektivnější. B Borůvkův algoritmus: v každém kroku dochází ke spojení aktuálního stromu s nejbližším jiným stromem. S využitím speciálních datových struktur je pro grafy s velkým počtem hran velmi rychlý. B Jarníkův algoritmus je vlastně obdobou Borůvková algoritmu s tím rozdílem, že v každém kroku bereme tentýž strom, který obohacujeme spojením s dalším stromem. Opět je výhodnější jej použít pro grafy s velkým počtem hran. 17. 10. 2017 21 / 37 Prohrnování silnic - řešení Řešení pomocí Kruskalova algoritmu Prohrnování silnie - řešení Řešení pomocí Kruskalova algoritmu: 17. 10. 2017 22 / 37 Úloha o třech nádobách Zadání: Mějme plnou nádobu vody o objemu 8 litrů a dvě prázdné nádoby s objemy 5 a 3 litry. Jakým způsobem musíme přelévat vodu tak, abychom nakonec dostali dvakrát 4 litry? Poznámka: Ani jedna z nádob nemá měrnou stupnici. 8 litrů 5 litrů 3 litry Autor prvního řešení z r. 1893: Georges Edouard Auguste Brunel (1856-1900) 17. 10. 2017 23 / 37 Úloha o třech nádobách - jak řešit pomocí grafů □ Objem tří nádob zapisovat do návěští vrcholů - trojice přirozených čísel k) včetně nuly, přičemž / < 8,j < 5, k < 3. B Vrcholy jsou vlastně "stavy", v jakých mohou jednotlivé nádoby být. Je-li možné přejít z jednoho stavu do druhého, umístíme mezi ně hranu či šipku ("orientovanou hranu"). B Existují hrany, u kterých záleží na pořadí počátečního a koncového vrcholu (viz červená šipka). □ Řešením úlohy je nalezení cesty o co nejmenším počtu hran (šipek) ze stavu (8, 0, 0) do stavu (4, 4, 0). 17. 10. 2017 24 / 37 Úloha o třech nádobách - stavové pole 17. 10. 2017 25 / 37 Úloha o třech nádobách - řešení Řešení: (8,0,0) ->3 (5, o, 3) ^3 (5, 3, 0) ^3 (2, 3, 3) ^2 (2, 5, 1) ^5 (7, o, 1) -»•1 (7, 1, 0) ^3 (4, 1, 3) ^3 (4, 4, 0) 17. 10. 2017 26 / 37 Úloha Vlk, koza, zelí Zadání: Vesničan se vrací z trhu domů. Má s sebou kozu, vlka a v ruce hlávku zelí. Najednou přišel k řece. Na břehu má přivázanou malou loď. Už chce nasednout, když tu ho náhle dobrá nálada opouští. Totiž, do té lodičky se všechno naráz nevejde. A když tu nechá vlka samotného, vlk sní kozu. Když tu nechá kozu, ta sní zelí. Jak dostane vlka, kozu i zelí na druhou stranu? Do loďky se mu vejde jen jedna věc. A na žádném z břehů nesmí nechat samotného vlka s kozou nebo kozu a zelí. 17. 10. 2017 27 / 37 Úloha Vlk, koza, zelí Zadání: Vesničan se vrací z trhu domů. Má s sebou kozu, vlka a v ruce hlávku zelí. Najednou přišel k řece. Na břehu má přivázanou malou loď. Už chce nasednout, když tu ho náhle dobrá nálada opouští. Totiž, do té lodičky se všechno naráz nevejde. A když tu nechá vlka samotného, vlk sní kozu. Když tu nechá kozu, ta sní zelí. Jak dostane vlka, kozu i zelí na druhou stranu? Do loďky se mu vejde jen jedna věc. A na žádném z břehů nesmí nechat samotného vlka s kozou nebo kozu a zelí. Řešení: Nejprve si označíme účastníky převozu. Vlk, Koza, Zelí a Převozník. Stavy grafu budou dvojice, které vzniknou rozkladem množiny {V, K,Z, P} na dvě podmnožiny reprezentující objekty na levém a pravém břehu. Počátečním stavem je tedy dvojice ({V, K,Z, P},0), cílem je dojít k vrcholu (0,{\/,/<,Z, P}). 17. 10. 2017 27 / 37 Úloha Vlk, koza, zelí - stavové pole K V P Z P K V Z K p v z P K v z P K V Z K Z P V P K Z v v P K Z p v K Z P K V Z V Z P K P V Z K Z P K V p z K V Červeně jsou označené nepovolené stavy a hrany s nimi incidentní. 17. 10. 2017 28 / 37 Úloha Vlk, koza, zelí-řešení K V P Z P K V Z K p v z P K v z P K V Z K Z P V P K Z v v P K Z p v K Z P K V Z V Z P K | P V z K z P K V p z K V K V P Z P K V Z K p v z P K v z P K V Z K Z P V P K Z v v P K Z p v K Z P K V Z V Z P K P V Z K Z P K V p z K V Zeleně je vyznačena nej kratší cesta, která prochází povolenými stavy. 17. 10. 2017 29 / 37 Hledání nejkratšŕ cesty Mějme ohodnocený (vážený) graf G — {V^ E). Každé hraně e G E je dáno reálné nezáporné číslo i/i/(e), tzv. ohodnocení (váha) hrany. V teorii grafů se můžeme setkat s těmito velmi podobnými problémy: H Shortest path: Najděte nejkratší cestu z iniciálního vrcholu s £ V do cílového vrcholu t G V y grafu G. B Single source shortest path: Najděte nejkratší cestu z iniciálního vrcholu a £ V do všech ostatních uzlů grafu G. El AM pairs shortest path: Najděte nejkratší cestu mezi každou dvojicí vrcholů grafu G. Poznámka: K řešení prvních dvou problémů se používá Dijkstrův algoritmus. Je možné jej použít i pro řešení 3. problému (aplikujeme jej pro každý vrchol grafu zvlášť), efektivnější metodou je však Floyd-Warshallův algoritmus. 17. 10. 2017 30 / 37 Dijkstrův algoritmus - inicializace Na počátku algoritmu vložíme do návěští iniciálního uzlu A hodnotu A/0, do návěští ostatních uzlů X, jejichž vzdálenost od A zatím neznáme, zapíšeme X/oo, viz následující obrázek. < cd? ► < ± > < ► -š -O q, O 17. 10. 2017 31 / 37 Dijkstrův algoritmus - procházení grafu Opakovaně provádíme následující tři kroky, dokud nezpracujeme všechny vrcholy: O Mezi nezpracovanými vrcholy najdeme uzel X/n s nejmenší vzdáleností n od iniciálního vrcholu A. Q Pro každou hranu e vedoucí z uzlu X/n do nezpracovaného vrcholu Y/m provedeme následující: ■ je-li m > n + i/i/(e), změníme aktuální vzdálenost uzlu Y od iniciálního uzlu A na m = n + w(e), ■ v opačném případě ponecháme návěští uzlu Y beze změny. El Označíme uzel X jako zpracovaný. 17. 10. 2017 32 / 37 Příklad použití Dijkstrova algoritmu Počátek algoritmu - neorientovaný graf o šesti uzlech A, B, C, D, E, F, přičemž vrchol A je iniciální. 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Uzel A se aktuálně zpracovává A/0 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Mění se návěští uzlů B, D, E (dosud nezpracovaní sousedé vrcholu A) A/0 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Z nezpracovaných vrcholů má nejmenší vzdálenost uzel B A/0 Příklad použití Dijkstrova algoritmu Uzel B se aktuálně zpracovává, vrchol A je označen jako zpracovaný 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Mění se návěští uzlů C, E (dosud nezpracovaní sousedé vrcholu B) 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Z nezpracovaných vrcholů má nejmenší vzdálenost uzel E Příklad použití Dijkstrova algoritmu Uzel E se aktuálně zpracovává, vrchol B je označen jako zpracovaný 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Mění se návěští uzlů C, D, F (dosud nezpracovaní sousedé vrcholu E) 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Z nezpracovaných vrcholů má nejmenší vzdálenost uzel C Příklad použití Dijkstrova algoritmu Uzel C se aktuálně zpracovává, vrchol E je označen jako zpracovaný 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Mění se návěští uzlu F (dosud nezpracovaný soused vrcholu C) < cd? ► < ± > < ► -š -O q, O 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Z nezpracovaných vrcholů má nejmenší vzdálenost uzel F F/5 Příklad použití Dijkstrova algoritmu Uzel F se aktuálně zpracovává, vrchol C je označen jako zpracovaný F/5 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Uzel F nemá nezpracované sousedy, je označen jako zpracovaný 4 ^ >■ < ► 4 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Z nezpracovaných vrcholů zbývá pouze vrchol D, je označen jako aktuálně zpracovávaný. A/0 17. 10. 2017 33 / 37 Příklad použití Dijkstrova algoritmu Uzel D nemá nezpracované sousedy. Je označen jako zpracovaný Konec algoritmu. F/5 17. 10. 2017 33 / 37 Dijkstrův algoritmus - poznámky H Dijkstrův algoritmus lze použít i pro neohodnocené grafy - postačí každé hraně přidat ohodnocení 1. B Dijkstrův algoritmus lze použít i pro orientované grafy, tj. grafy, v nichž má hrana směr. B Dijkstrův algoritmus nelze spolehlivě použít pro ohodnocené grafy, ve kterých je váha některých hran záporná. 17. 10. 2017 34 / 37 Dijkstrův algoritmus - příklad Nalezněte (pomocí Dijkstrova algoritmu) nej kratší cestu od uzlu A ke všem ostatním vrcholům grafu zadaného následujícím obrázkem. 17. 10. 2017 35 / 37 Dijkstrův algoritmus - řešení příkladu 17. 10. 2017 36 / 37 Použité zdroje Q FUCHS, Eduard. Diskrétní matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001. 178 s. ISBN 80-210-2703-7. B MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6. B CERNY, Jakub. Základní grafové algoritmy. Dostupné z: http://algoritmy.eu/zga/ ✓ _ □ PELANEK, Radek a kol. Teorie grafů - Poznámky pro učitele. Dostupné z: https://www.fi.muni.cz/ xpelanek/ucitele/?action=logicke H ŠIŠMA, Pavel. Teorie grafů 1736-1963. 1. vyd. Praha: Přírodovědecká fakulta Masarykovy univerzity v Brně, 1997. ISBN 80-7196-065-9. □ MASILKO, Lukáš, PECL, Jiří. Adaptace matematických algoritmů. Dostupné z: https://www.teiresias.muni.cz/amalg/www/cs/ 17. 10. 2017 37 / 37