Devátá sada domácích úloh k přednášce MB103
Příklad 1. Označme vrcholy v grafu K6 postupně čísly 1, 2, . . . , 6. Napište posloupnost hran grafu
K6 tak, jak je bude procházet algoritmus ,,prohledávání do hloubky , bude-li počátečním vrcholem
vrchol 5 a hrany ze zpracovávaného vrcholu budeme procházet postupně podle velikosti druhého
koncového vrcholu hrany (od nejmenšího).
Příklad 2. Uvažujme modifikovaný Dijkstrův algoritmus pro hledání minimálních cest z daného
vrcholu v ohodnoceném grafu. Oproti algoritmu z přednášky provedeme jedinou změnu: 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 konečnými hodnotami d(v). Rozhodněte, zda
takový algoritmus nalezne minimální cesty z daného vrcholu.
Příklad 3. 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.