Rámcová náplň cvičení

Eulerovské grafy

Pojednání o známé hříčce zvané kreslení jedním tahem, její historii (7 mostů) a Eulerovo řešení - viz dodatečné sekce v přednáškových materiálech. Vše hravě a zajímavě pojaté...

Vzdálenost v grafech

Bude probrána především základní grafová vzdálenost (počtem hran cesty) a ukázáno zobecnění na ohodnocenou vzdálenost, kdy "délky hran" jsou obecně různé od 1.
Jednoduché důkazy ohledně grafové vzdálenosti.

Opakování isomorfismu

Ve zbytku času se opět podíváme na problematiku isomorfismu grafů. Příklady je možné volit z odpovědníkových otázek a podobně. Při rozhodování isomorfismu grafů nyní využijeme také vzdálenosti (jako například kolik vrcholů stupně 2 je do vzdálenosti 2 či 3 od daného vrcholu, apod).
V návaznosti případné vysvětlení heuristického algoritmu pro isomorfismus...

Možné příklady k procvičení vzdálenosti

• Určete vzdálenost mezi konkrétními dvěma vrcholy ve vybraném grafu z obrázků výše. Řešte i příklady, kdy odpověď není "na první pohled jasná".
• Určete poloměr a průměr ve vybraném grafu z obrázků výše. Kolik vrcholů obsahuje centrum tohoto grafu a kolik dvojic vrcholů má vzdálenost rovnou průměru grafu?

• Určete ohodnocenou vzdálenost z A do B v každém z následujících grafů:
  

Procházení grafu, algoritmy - jen volitelné

Tato část cvičení je volitelná pro případ, že zbývá volný čas...

Rozebrání způsobů procházení grafu, ruční ukázky běhů algoritmů.

• Tuto část není až tak nutno probírat na cvičeních, neboť průběh algoritmů vázajících se k procházení grafu byl důkladně vysvětlen na přednášce a stejně bude znovu probírán na jiných předmětech o návrhu algoritmů.
• Pokud je přesto volný čas, lze například dokazovat, že obecné schéma procházení grafu probere všechny vrcholy a hrany souvislé komponenty. Také je možno probrat důkazy korektnost Dijkstrova a Jarníkova algoritmu.