Sada domácích úloh k přednášce Matematika III
k odevzdání v týdnu 13 ­ 16. listopadu 2006
Příklad 1. Uvažujme modifikovaný Dijkstrův algoritmus pro hledání minimální cesty mezi dvěma
vrcholy v ohodnoceném grafu: algoritmus bude v okamžiku výběru množiny aktivních vrcholů
vybírat nikoliv množinu s minimálními hodnotami d(v), ale množinu vrcholů s maximálními hod-
notami d(v). Udejte příklad grafu a v něm dvou vrcholů, mezi kterými nalezne tato modifikace
minimální cestu rychleji, než algoritmus uvedený na přednášce.
Příklad 2. Dokažte, že hamiltonovský graf musí být vrcholově 2-souvislý. Udejte příklad grafu,
který je vrcholově 2-souvislý a přesto v něm neexistuje hamiltonovská kružnice.
Příklad 3.
Dokažte nebo vyvraťte:
a) Každý graf s méně než devíti hranami je rovinný.
b) Graf, který není rovinný, není ani hamiltonovský.
c) Graf, který není rovinný, je hamiltonovský.
d) Graf, který není rovinný, není eulerovský.
e) Graf, který není rovinný, je eulerovský.
f) Každý hamiltonovský graf je rovinný.
g) Každý eulerovský graf je rovinný.