Matematika III, 9. cvičení
Pojmy k zopakování
• Cesta v grafu, sled
• Dijkstrův algoritmus, Bellman-Forduv algoritmus, Floyd-Warshaľluv algoritmus
• Vzdálenost vrcholů v neorientovaném grafu
Příklad 172. Kolik různých cest existuje v úplném grafu      mezi dvěma různými vrcholy u a
v?
Příklad 173. Dokažte, že vyskytuje-li se v uzavřeném sledu S některá hrana pouze jednou, tak sled S obsahuje cyklus.
Příklad 174. Máme osmilitrovou nádobu s vínem a dvě prázdné nádoby - pětilitrovou a třílitrovou. Rozdělte osm litrů na ětyři a čtyři litry jen s užitím těchto nádob, bez použití odměrky. Úlohu namodelujte grafem a najděte nejkratší řešení a popište všechna přípustná řešení.
Nápověda: Sestrojte graf, kde uzly budou všechny stavy, které mohou v nádobách nastat.
Příklad 175. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do všech ostatních vrcholů.
Výsledek. V abecedním pořadí je to: 0,1,3,6,2,5.
Příklad 176. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do vrcholu g.
Výsledek. V abecedním pořadí vrcholů jsou vzdálenosti od a: 0,21,16,8,20,14,19. Tedy g má vzdálenost 19.
Příklad 177. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do všech ostatních vrcholů.
■29
Výsledek. V abecedním pořadí vrcholů jsou vzdálenosti od a: 0,3,2,1,1.
Příklad 178. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do všech ostatních vrcholů.
	K.--f
X 1	\ 7 i \y
f\	A X
12	4
Příklad 179. V následujícím ohodnoceném grafu najděte nejkratší cesty z vrcholu a do všech ostatních vrcholů pomocí Bellman-Fordova algoritmu.
Příklad 180. V následujícím ohodnoceném grafu najděte nejkratší cesty z vrcholu a do všech ostatních vrcholů pomocí Bellman-Fordova algoritmu.
Příklad 181. V následujícím ohodnoceném grafu najděte nejkratší cesty z vrcholu a do všech ostatních vrcholů pomocí Bellman-Fordova algoritmu.
30
Příklad 182. V následujících ohodnocených grafech najděte nejkratší cesty z vrcholu a do všech ostatních vrcholů pomocí Bellman-Fordova algoritmu.
Příklad 185. Bude Dijkstrův algoritmus pracovat správně, pokud sice graf obsahuje hrany záporné délky, ale každý jeho cyklus má kladnou délku?
Výsledek. Ne (Najděte protipříklad)
Příklad 186. Uvažujme následující algoritmus na hledání nejkratší cesty z vrcholu a do všech ostatních vrcholů v orientovaných grafech s obecným ohodnocením hran (tedy i záporným): Vezmeme dostatečně velkou konstantu a přičteme ji k ohodnocení každé hrany. Tím získáme nezáporné ohodnocení hran. Potom už můžeme použít Dijkstrův algoritmus. Nalezená nejkratší cesta bude stejná jako nejkratší cesta v grafu s původním ohodnocením. Dokažte, že navrhovaná metoda funguje, nebo nalezněte protipříklad.
Příklad 187. Uveďte příklad ohodnoceného grafu na čtyřech vrcholech, na kterém selže Dijkstrův algoritmus.
Příklad 188. Je dán graf, jehož hrany jsou ohodnoceny kladnými čísly. Délka cesty se počítá jako součin ohodnocení hran ležících na cestě. Najděte nejkratší cestu z vrcholu a do vrcholu b.
31
Nápověda: Převeďte součin na součet (logaritmus).
Příklad 189. Dostaneme ohodnocený orientovaný graf G = (V; E), dvě neprázdné disjunktní množiny A, B C V . Najděte nejkratší cestu, která začíná ve vrcholu množiny A a končí ve vrcholu množiny B.
Nápověda: Převeďte tento problém na běžný problém nejkratší cesty.
Výsledek. Přidejme do grafu vrcholy u,v, přičemž veďme navzájem stejně ohodnocené hrany z vrcholu u do vrcholů množiny A a stejně ohodnocené hrany z vrcholů množiny B do vrcholu v. Hledanou nejkratší cestou potom bude nejkratší cesta mezi vrcholy u, v.
Příklad 190. Mějme ohodnocený neorientovaný graf, kde kromě hran jsou ohodnoceny i vrcholy. Nalezněte cestu z vrcholu s do vrcholu t tak, aby součet hranových i vrcholových ohodnocení po této cestě byl co nejmenší.
Nápověda: Převeďte tento problém na běžný problém nejkratší cesty.
Výsledek. Zdvojme každý z uzlů a mezi nimi veďme hranu, která bude ohodnocená jako zdvojovaný vrchol.
Příklad 191. Jaká největší vzdálenost může být mezi dvěma vrcholy kružnice délky 9, jejíž hrany jsou ohodnoceny čísly 1, 2,..., 8, 9 v libovolném pořadí?
Výsledek. 22
Příklad 192. Určete, kolik nejméně hran musíme přidat do grafu C%, aby vzdálenost mezi libovolnými dvěma vrcholy byla nejvýše 2.
Výsledek. 2
Příklad 193. Určete, kolik nejvýše hran můžeme odebrat z K^, (resp. Kq), aby vzdálenost mezi každými dvěma vrcholy byla menší nebo rovna dvěma.
Výsledek. 5 (resp. 7)
32