Cvičení 5

Úloha 5.1

Pro graf na snímku č. 3 z prezentace kostry.pdf odsimulujte ručně na papír generování všech koster tvorbou stromu řešení (snímek č. 10). Postačí, vygenerujete-li 10 řešení.

Úloha 5.2

Zjistěte, kolik koster má graf na obr. 1. Nalezněte minimální kostru tohoto grafu pomocí Borůvkova algoritmu. Rozkreslete přidávání hran.

Obrázek 1: Zadaný graf

Řešení: Řešení úlohy 5.2

Úloha 5.3

Nalezněte minimální kostru grafu z úlohy 5.2 pomocí Jarníkova algoritmu. Rozkreslete přidávání hran.

Řešení: Řešení úlohy 5.3

Úloha 5.4

Navrhněte rozptylovací funkci a rozptylovací tabulku pro ukládání celých čísel v rozsahu 0 až 1000.

Řešení: Řešení úlohy 5.4