Domácí úlohy z minulého týdne Návodné úlohy Drsná matematika III ­ 6. demonstrovaná cvičení Grafové algoritmy Martin Panák Masarykova univerzita Fakulta informatiky 14.11. 2006 Domácí úlohy z minulého týdne Návodné úlohy 1 Domácí úlohy z minulého týdne Příklad 1. Příklad 1. Příklad 2. Příklad 2. Příklad 3. Příklad 3. 2 Návodné úlohy Dijkstrův algoritmus Dijkstrův algoritmus Eulerovské grafy Hamiltonovské grafy Rovinné grafy Eulerova formule Eulerova formule Eulerova formule Eulerova formule Domácí úlohy z minulého týdne Návodné úlohy Určete, které z následujících neorientovaných grafů jsou izomorfní: Domácí úlohy z minulého týdne Návodné úlohy Určete, které z následujících neorientovaných grafů jsou izomorfní: Řešení. Žádné dva 2 Domácí úlohy z minulého týdne Návodné úlohy Pomocí matice sousednosti je dán neorientovaný graf o pěti vrcholech (nazývejme je 1, . . . , 5. Nakreslete jej v rovině a zjistěte, kolik sledů délky čtyři vede z vrcholu 1 do vrcholu 5: 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 . Domácí úlohy z minulého týdne Návodné úlohy Pomocí matice sousednosti je dán neorientovaný graf o pěti vrcholech (nazývejme je 1, . . . , 5. Nakreslete jej v rovině a zjistěte, kolik sledů délky čtyři vede z vrcholu 1 do vrcholu 5: 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 . Řešení. 26. 2 Domácí úlohy z minulého týdne Návodné úlohy Rozhodněte, zda existují grafy s následujícím skóre (pokud ano, nakreslete je): a) (5, 5, 4, 2, 1, 1, 1, 1), b) (5, 5, 4, 4, 3, 1, 1, 1). Domácí úlohy z minulého týdne Návodné úlohy Rozhodněte, zda existují grafy s následujícím skóre (pokud ano, nakreslete je): a) (5, 5, 4, 2, 1, 1, 1, 1), b) (5, 5, 4, 4, 3, 1, 1, 1). Řešení. Po použití algoritmu z přednášky: a) ne, b) ano. 2 Domácí úlohy z minulého týdne Návodné úlohy 1 Domácí úlohy z minulého týdne Příklad 1. Příklad 1. Příklad 2. Příklad 2. Příklad 3. Příklad 3. 2 Návodné úlohy Dijkstrův algoritmus Dijkstrův algoritmus Eulerovské grafy Hamiltonovské grafy Rovinné grafy Eulerova formule Eulerova formule Eulerova formule Eulerova formule Domácí úlohy z minulého týdne Návodné úlohy Konečnost Dijkstrova algoritmu Domácí úlohy z minulého týdne Návodné úlohy Konečnost Dijkstrova algoritmu Výpočet matice minimálních vzdáleností Domácí úlohy z minulého týdne Návodné úlohy Eulerovské grafy Domácí úlohy z minulého týdne Návodné úlohy Hamiltonovské grafy Domácí úlohy z minulého týdne Návodné úlohy Domácí úlohy z minulého týdne Návodné úlohy v + s - h = 2. Domácí úlohy 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í úlohy 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í úlohy 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.