Domácí úkoly z minulého týdne Návodné úlohy Drsná matematika III – 9. demonstrovaná cvičení Grafové algoritmy Martin Panák Masarykova univerzita Fakulta informatiky 15.11. 2011 Domácí úkoly z minulého týdne Návodné úlohy Plán přednášky 1 Domácí úkoly z minulého týdne 2 Návodné úlohy Eulerovské grafy Hamiltonovské grafy Rovinné grafy Eulerova formule Eulerova formule Eulerova formule Eulerova formule Domácí úkoly z minulého týdne Návodné úlohy Příklad 1. Udejte příklad grafu, ve kterém se vyskytuje záporně ohodnocená hrana a přesto Dijkstrův algoritmus spočítá správně délky nejkratších cest z nějakého vrcholu (ale ne ze všech). Udejte příklad grafu, ve kterém se vyskytuje záporně ohodnocená hrana a přesto Dijkstrův algoritmus spočítá správně délky nejkratších cest z ze všech vrcholů. Udejte příklad grafu a jeho vrcholu takového, že výstup Dijkstrova algoritmu nebudou nejkratší cesty z daného algoritmu. (Uveďte graf, vrchol ze kterého má Dijkstrův algoritmus začínat, délky nejkratších cest z něho podle Dijkstrova algoritmu a skutečné délky nejkratších z něj.) Domácí úkoly z minulého týdne Návodné úlohy Příklad 2. Určete všechna n ∈ N pro která platí: Odebráním libovolných dvou hran z grafu Kn vznikne nejvýše (n − 3)-souvislý graf. Domácí úkoly z minulého týdne Návodné úlohy Příklad 3. Uvažme následující algoritmus pro hledání nejkratších cest v konečném neorientovaném grafu i se záporně ohodnocenými hranami. Označme nejmenší hodnotu hrany h. Ke všem hranám přičtěme |h|. Nyní jsou všechny hrany ohodnoceny nezáporně. Vybereme vrchol (řekněme v) a proběhneme Dijkstrův algoritmus z něj na grafu s takto nezáporně ohodnocenými hranami. Dokažte či vyvraťte, že tímto postupem dostaneme nejkratší cesty z vrcholu v v původním grafu (od délky nejkratší cesty do libovolného vrcholu nalezenou Dijkstrovým algoritmem bychom odečetli k · |h|, kde k je délka cesty). Domácí úkoly z minulého týdne Návodné úlohy Plán přednášky 1 Domácí úkoly z minulého týdne 2 Návodné úlohy Eulerovské grafy Hamiltonovské grafy Rovinné grafy Eulerova formule Eulerova formule Eulerova formule Eulerova formule Domácí úkoly z minulého týdne Návodné úlohy Eulerovské grafy Domácí úkoly z minulého týdne Návodné úlohy Hamiltonovské grafy Domácí úkoly z minulého týdne Návodné úlohy Domácí úkoly z minulého týdne Návodné úlohy v + s − h = 2. Domácí úkoly z minulého týdne Návodné úlohy v + s − h = 2. Kolik nejméně hran může mít jedenáctistěn? Domácí úkoly z minulého týdne Návodné úlohy v + s − h = 2. Kolik nejméně hran může mít jedenáctistěn? Příklad s torem. Domácí úkoly z minulého týdne Návodné úlohy v + s − h = 2. Kolik nejméně hran může mít jedenáctistěn? Příklad s torem. v + s + h = χ(g), kde χ(g) = 2 − 2g, g je genus povrchu.