Domácí úlohy z minulého týdne Hledání minimální kostry Drsná matematika III ­ 10. demonstrovaná cvičení Kostry grafů Martin Panák Masarykova univerzita Fakulta informatiky 21.11. 2006 Domácí úlohy z minulého týdne Hledání minimální kostry 1 Domácí úlohy z minulého týdne Příklad 1 Příklad 2 Příklad 3 2 Hledání minimální kostry Borůvkův algoritmus Primův algoritmus Graf koster Heuristika na hledání minimální cesty spojující všechny vrcholy Domácí úlohy z minulého týdne Hledání minimální kostry Příklad 1. Uvažujme modifikovaný Dijkstrův algoritmus pro hledání minimální cesty mezi dvěma vrcholy v ohodnoceném grafu: algoritmus bude probírat hrany vedoucí z aktivního vrcholu nikoliv od nejkratší, ale od nejdelší. Udejte příklad grafu a v něm dvou vrcholů, mezi kterými nalezne tato modifikace minimální cestu rychleji, než algoritmus uvedený na přednášce. Domácí úlohy z minulého týdne Hledání minimální kostry Příklad 2. Dokažte, že vrcholový graf musí být vrcholově 2-souvislý. Udejte příklad grafu, který je vrcholově 2-souvislý a přesto v něm neexistuje hamiltonovská kružnice. Domácí úlohy z minulého týdne Hledání minimální kostry Příklad 2. Dokažte, že vrcholový graf musí být vrcholově 2-souvislý. Udejte příklad grafu, který je vrcholově 2-souvislý a přesto v něm neexistuje hamiltonovská kružnice. Řešení. V hamiltonovském grafu vedou mezi libovolnými dvěma uzly dvě neprotínající se cesty (,,oblouky hamiltonovské kružnice). Odstraněním jednoho bodu, se tedy zjevně neporuší souvislost grafu (odstraněný bod může ležet pouze na jedné ze dvou cest). 2 Domácí úlohy z minulého týdne Hledání minimální kostry Příklad 3. Dokažte nebo vyvraťte: a) Každý graf s méně než devíti hranami je rovinný. b) Graf, který není rovinný, není ani hamiltonovský. c) Graf, který není rovinný, je hamiltonovský. d) Graf, který není rovinný, není eulerovský. e) Graf, který není rovinný, je eulerovský. f) Každý hamiltonovský graf je rovinný. g) Každý eulerovský graf je rovinný. Domácí úlohy z minulého týdne Hledání minimální kostry Příklad 3. Dokažte nebo vyvraťte: a) Každý graf s méně než devíti hranami je rovinný. b) Graf, který není rovinný, není ani hamiltonovský. c) Graf, který není rovinný, je hamiltonovský. d) Graf, který není rovinný, není eulerovský. e) Graf, který není rovinný, je eulerovský. f) Každý hamiltonovský graf je rovinný. g) Každý eulerovský graf je rovinný. Řešení. a) Ano. Triviální důsledek charakterizace rovinných grafů (K3,3 i K5 mají minimálně 9 hran) b) Ne. (K3,3) c) Ne. d) Ne. (Protipříklad K5) e) Ne. (K3,3) f) Ne. (K5) Domácí úlohy z minulého týdne Hledání minimální kostry 1 Domácí úlohy z minulého týdne Příklad 1 Příklad 2 Příklad 3 2 Hledání minimální kostry Borůvkův algoritmus Primův algoritmus Graf koster Heuristika na hledání minimální cesty spojující všechny vrcholy Domácí úlohy z minulého týdne Hledání minimální kostry Borůvkův algoritmus Udělej graf S složený z vrcholů grafu G; dokud má S více než jednu komponentu opakuj: pro každý strom T v S najdi nejmenší hranu spojující T s G \ T, tuto hranu přidej do E; všechny hrany z E přidej do S; Domácí úlohy z minulého týdne Hledání minimální kostry Primův algoritmus Buď T jediný vrchol; dokud T má méně než n vrcholů, najdi nejmenší hranu spojující T a G \ T a přidej ji do T; Domácí úlohy z minulého týdne Hledání minimální kostry Graf koster Uvažme graf koster souvislého grafu G o n vrcholech: vrcholy jsou kostry G, dva vrcholy (kostry) jsou spojeny hranou, jestliže mají právě n - 2 společných hran. Ukažte, že graf koster souvislého grafu je souvislý. Domácí úlohy z minulého týdne Hledání minimální kostry Graf koster Uvažme graf koster souvislého grafu G o n vrcholech: vrcholy jsou kostry G, dva vrcholy (kostry) jsou spojeny hranou, jestliže mají právě n - 2 společných hran. Ukažte, že graf koster souvislého grafu je souvislý. Počet koster v grafu Určete počet různých koster následujícího grafu. Určete tento počet až na isomorfismus. Domácí úlohy z minulého týdne Hledání minimální kostry Heuristika na hledání minimální cesty spojující všechny vrcholy C je prázdná množina; Dokud C není hledaná cesta, přidej do C minimální hranu takovou, že po jejím přidání bude C tvořeno disjunktními cestami;