od toby22 » 16. 6. 2020 17:53
TEORIE:
1) Popsat hledání nejkratších cest (hlavně relaxace - invariant, lemmata) a rozebrat Dijkstru – složitost, kdy se vyplatí, kdy ne, jaký má problém se zápornými hranami,...
2) (a,b) stromy
PŘÍKLADY:
1)Stavíme dům a sestavíme si závislostní graf všech činností. O vrcholu tohoto grafu řekneme, že je kritický, pokud by zpomalení příslušné činnosti způsobilo pozdější dokončení celého domu. Při řízení stavby si proto na takové vrcholy musíme dávat pozor. Vymyslete, jak je všechny najít.
2)Pro neorientovaný ohodnocený graf G=(V,E,w) a množinu vrcholů S⊆V navrhněte algoritmus, který najde minimální kostru grafu G, u které jsou všechny vrcholy z množiny S listy nalezené kostry. Ostatní vrcholy mohou být také listy, tedy například pro S=∅ hledáme obvyklou minimální kostru.
TEORIE:
1) Popsat hledání nejkratších cest (hlavně relaxace - invariant, lemmata) a rozebrat Dijkstru – složitost, kdy se vyplatí, kdy ne, jaký má problém se zápornými hranami,...
2) (a,b) stromy
PŘÍKLADY:
1)Stavíme dům a sestavíme si závislostní graf všech činností. O vrcholu tohoto grafu řekneme, že je kritický, pokud by zpomalení příslušné činnosti způsobilo pozdější dokončení celého domu. Při řízení stavby si proto na takové vrcholy musíme dávat pozor. Vymyslete, jak je všechny najít.
2)Pro neorientovaný ohodnocený graf G=(V,E,w) a množinu vrcholů S⊆V navrhněte algoritmus, který najde minimální kostru grafu G, u které jsou všechny vrcholy z množiny S listy nalezené kostry. Ostatní vrcholy mohou být také listy, tedy například pro S=∅ hledáme obvyklou minimální kostru.