Matematika III, 9. cvičení
Pojmy k zopakování
• Cesta v grafu, sled
• Dijkstruv algoritmus, Bellman-Forduv algoritmus, Floyd-WarshallUv algoritmus
• Vzdálenost vrcholu v neorientovaném grafu
Příklad 172. Kolik různých cest existuje v úplném grafu K6 mezi dvěma různými vrcholy u a v?
Výsledek. 16
Příklad 173. Kolik různých cest existuje v úplnem grafu Kn mezi dvema různými vrcholy u a
v?
Výsledek. 2n-2
Příklad 174. Dokazte, ze vyskytuje-li se v uzavšenem sledu S nekterý hrana pouze jednou, tak sled S obsahuje cyklus.
Příklad 175. Mame osmilitrovou nadobu s vínem a dve pmzdne nadoby - petilitrovou a trílitrovou. Rozdelte osm litru na ctyri a ctyri litry jen s uzitím techto nídob, bez pouzití odmerky. Ulohu namodelujte grafem a najdete nejkratsí řešení a popište všechna prípustna řešení.
Napoveda: Sestrojte graf, kde uzly budou všechny stavy, ktere mohou v nadobích nastat.
Příklad 176. V nasledujúcim grafu pomocí Dijkstrova algoritmu najdete nejkratsí cestu z vrcholu a do všech ostatních vrcholů.
28
Příklad 178. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do všech ostatních vrcholu.
Příklad 179. V následujícím grafu pomocí Dijkstrova algoritmu najděte nejkratší cestu z vrcholu a do všech ostatních vrcholu.
Příklad 180. V nasledujícím ohodnoceném grafu najdete nejkratší cesty z vrcholu a do všech ostatních vrcholu pomocí Bellman-Fordova algoritmu.
Příklad 181. V nasledujícím ohodnoceném grafu najdete nejkratší cesty z vrcholu a do všech ostatníích vrchollu pomocíí Bellman-Fordova algoritmu.
Příklad 182. V nísledujícím ohodnoceném grafu najdete nejkratší cesty z vrcholu a do všech ostatníích vrchollu pomocíí Bellman-Fordova algoritmu.
29
Příklad 183. V následujících ohodnocených grafech najděte nejkratší cesty z vrcholu a do všech ostatních vrcholU pomocí Bellman-Fordova algoritmu.
Příklad 186. Bude Dijkstrův algoritmus pracovat správně, pokud sice graf obsahuje hrany záporné délky, ale každý jeho cyklus ma kladnou délku?
Výsledek. Ano
Příklad 187. Uvažujme nasledujécé algoritmus na hledané nejkratší cesty z vrcholu a do všech ostatných vrcholu v orientovaných grafech s obecným ohodnocením hran (tedy i zépornym): Vezmeme dostatečně velkou konstantu a pšicteme ji k ohodnocené každe hrany. Tím získame nezaporne ohodnocené hran. Potom už můžeme použít Dijkstrův algoritmus. Nalezena nejkratsé cesta bude stejna jako nejkratší cesta v grafu s původním ohodnoceném. Dokažte, že navrhovana metoda funguje, nebo naleznete protipžéklad.
Příklad 188. Uved'te príklad ohodnoceneho grafu na ctyrech vrcholech, na kterem selže Dijkstrův algoritmus.
30
Příklad 189. 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 ceste. Najdete nejkratsí cestu z vrcholu a do vrcholu b.
.     2 _&
Nápověda: Preveďte součin na součet (logaritmus).
Příklad 190. Dostaneme ohodnocený orientovaný graf G = (V; E), dve neprazdne disjunktní mnoZiny A, B C V . Najdete nejkratsí cestu, která začína ve vrcholu mnoZiny A a končí, ve vrcholu mnoZiny B.
Napoveda: Preved'te tento problem na bečny problem nejkratsí cesty.
Vísledek. Přidejme do grafu vrcholy u, v, přičemž ved'me navzájem stejně ohodnocené hrany z vrcholu u do vrcholu množiny A a stejne ohodnocene hrany z vrcholu množiny B do vrcholu v. Hledanou nejkratsí cestou potom bude nejkratsí cesta mezi vrcholy u, v.
Příklad 191. Mčjme ohodnoceny neorientovany graf, kde krome hran jsou ohodnoceny i vrcholy. Naleznete cestu z vrcholu s do vrcholu t tak, aby součet hranovích i vrcholovych ohodnocení po tíeto cestče byl co nejmenčsíí.
Naípovčeda: Pčreved te tento problíem na bčečzníy problíem nejkratčsíí cesty.
Vísledek. Zdvojme kazdý z uzlu a mezi nimi ved'me hranu, ktera bude ohodnocená jako zdvojovaný vrchol.
Příklad 192. Jakí největší vzdalenost muče byt mezi dvema vrcholy kručnice delky 9, jejíz hrany jsou ohodnoceny císly 1, 2,..., 8,9 v libovolnem poradí?
Vísledek. 22
Příklad 193. Určete, kolik nejmene hran musíme pridat do grafu C6, aby vzdílenost mezi libovolními dvema vrcholy byla nejvyse 2.
31
Výsledek. 2
Příklad 194. Určete, kolik nejvýše hran můžeme odebrat z K5 (resp. K6), aby vzdálenost mezi každými dvěma vrcholy byla menši nebo rovna dvěma.
Výsledek. 5 (resp. 7)
32