(DeTtwcviemí
M<B101 -jaro 2012 12. listopadu 2012
Příklad 1. Užijte Dijkstrův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholů.
Q
3-
18    1    2    1    7   1 3 1
6
1^)
1
}—2—b—7
8 15 2
< 5
Příklad 2. Užijte Bellman-Fordův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholů. Procházejte graf zprava a shora.
18    1    2 1 2--Q \^-6^b
1 1
8
3
Příklad 3. Užijte Floyd-Warshallův algoritmus k nalezení nejkratších cest mezi všemi dvojicemi vrcholů. Vysvětlete, jak dochází k detekci záporných cyklů.
1
Příklad 4. Udejte příklad
(a) grafu s alespoň 4 vrcholy, který neobsahuje cyklus záporné délky a na němž dá Dijkstrův algoritmus chybný výsledek.
(b) grafu s alespoň 4 vrcholy, který obsahuje (alespoň jednu) nezápornou hranu a přesto na něm dá Dijkstrův algoritmus správný výsledek.
Příklad 5. Kolik nejvíce vrcholů může mít graf, který má všechny vrcholy stupně 3 a největší vzdálenost mezi dvěma vrcholy je 2?
Příklad 6. Hlavolam známý jako Hanojské věže má tři kolíky a sadu osmi disků (pro nás 3) různých velikostí. Na začátku je všech osm disků seřazeno podle velikosti na prvním kůlu. Úkolem je přemístit všechny disky na jiný kůl za dodržení následujících podmínek:
1. vždy se přesunuje pouze jeden disk,
2. nikdy nesmí ležet větší disk na menším.
Příklad 7. Najděte graf s co nej menším počtem hran na 2012 vrcholech, ve kterém je minimální i maximální vzdálenost dvou různých nesousedních vrcholů 2.
2