Osmá sada domácích úloh k přednášce Matematika III
Příklad 1. Udejte příklad grafu, ve kterém se vyskytuje záporně ohodnocená hrana a přesto Dijkstrův
algoritmus spočítá správně délky nejkratších cest z nějakého vrcholu (ale ne ze všech).
Udejte příklad grafu, ve kterém se vyskytuje záporně ohodnocená hrana a přesto Dijkstrův
algoritmus spočítá správně délky nejkratších cest z ze všech vrcholů.
Udejte příklad grafu a jeho vrcholu takového, že výstup Dijkstrova algoritmu nebudou nejkratší
cesty z daného algoritmu. (Uveďte graf, vrchol ze kterého má Dijkstrův algoritmus začínat, délky
nejkratších cest z něho podle Dijkstrova algoritmu a skutečné délky nejkratších z něj.)
Příklad 2. Určete všechna n ∈ N pro která platí: Odebráním libovolných dvou hran z grafu Kn
vznikne nejvýše (n − 3)-souvislý graf.
Příklad Uvažme následující algoritmus pro hledání nejkratších cest v konečném neorientovaném
grafu i se záporně ohodnocenými hranami. Označme nejmenší hodnotu hrany h. Ke všem hranám
přičtěme |h|. Nyní jsou všechny hrany ohodnoceny nezáporně. Vybereme vrchol (řekněme v) a
proběhneme Dijkstrův algoritmus z něj na grafu s takto nezáporně ohodnocenými hranami. Dokažte
či vyvraťte, že tímto postupem dostaneme nejkratší cesty z vrcholu v v původním grafu (od délky
nejkratší cesty do libovolného vrcholu nalezenou Dijkstrovým algoritmem bychom odečetli k · |h|,
kde k je délka cesty).