Petr Hliněný, FI MU Brno 1 FI: MA010: Kreslení grafů 11 Více o kreslení grafů Tato lekce se soustřeďuje na následující otázku: Jak vhodně nakreslíme nerovinný graf? Této otázce jsme se již implicitně věnovali u průsečíkového čísla grafu a nyní si ukážeme dva různé pohledy. Buď budeme grafy kreslit stále bez křížení, ale na tzv. "vyšší plochy" jako torus nebo projektivní rovina. Nebo zůstaneme v rovině, ale povolíme křížení hran a budeme hledat "esteticky pěkná" nakreslení. 2 Stručný přehled lekce * Klasifikace ploch a kreslení grafů na plochy, zakázané minory. * Trochu o zajímavém problému rovinného pokrytí. * Vysvětlení "pružinového" algoritmu pro kreslení grafů do roviny. Petr Hliněný, FI MU Brno 2 FI: MA010: Kreslení grafů 11.1 Kreslení grafů na plochy Nejprve si stručně uvedeme důležitý výsledek klasické topologie ­ klasifikaci ploch. Věta 11.1. Každá plocha (tj. kompaktní 2-manifold) je homeomorfní jedné z ­ S sféře. ­ Sh sféře s h přidanýma "ušima" (handle). ­ Nk sféře s k přidanými "křížícími místy" (crosscap). Definice: Crosscap na ploše je kružnice, jejíž protilehlé dvojice bodů jsou ztotožněny (kruhový vnitřek přitom ploše už nepatří). 2 Poznámka: Plocha S1 je známý torus, neboli povrch pneumatiky. Plocha N1 je projektivní rovina a vypuštěním kruhu z N1 vzniká známý Möbiův proužek. Plocha N2 je tzv. Kleinova láhev. 2 Plochy S a Sh jsou orientovatelné, kdežto Nk jsou neorientovatelné. 2 Lema 11.2. Máme-li plochu vzniklou ze sféry přidáním k > 2 crosscapů a h uší, tak je homeomorfní ploše vzniklé ze sféry přidáním k - 2 crosscapů a h + 1 uší. Petr Hliněný, FI MU Brno 3 FI: MA010: Kreslení grafů Definice 11.3. Nakreslení grafu G na plochu myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body na a hrany jako oblouky spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. 2 Na vyšší plochy přenášíme i další pojmy rovinného kreslení, jako pojem stěny. Definice: Nakreslení grafu G na plochu je buňkové, pokud je každá stěna homeomorfní otevřenému disku. 2 Fakt: Buňkové nakreslení grafu G je jednoznačně určeno svými stěnovými kružnicemi a jako takové definuje i plochu až na homeomorfismus. (Neboli plochu lze "slepit" z jednotlivých disků stěn podél společných hran stěnových kružnic.) 2 Tvrzení 11.4. Buňkové nakreslení grafu G na orientovatelnou plochu je jednoznačně určeno rotačním schématem vycházejících hran u svých vrcholů. (V případě neorientovatelných ploch je třeba ještě přidat jistá "znaménka".) Petr Hliněný, FI MU Brno 4 FI: MA010: Kreslení grafů Kreslení na určenou plochu Mnohé poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Věta 11.5. (Mohar) Pro každou pevnou plochu existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na , nebo určí minimální překážku nakreslitelnosti na . 2 Za poznamenání stojí, že obecnější problém určit "nejjednodušší" plochu, na kterou lze daný graf nakreslit, je už NP-těžký. Z jiné strany lze zobecňovat Kuratowského větu na vyšší plochy. Třebaže je známo, že takové zobecnění s konečným počtem překážek je platné pro každou plochu, konkrétní seznam zakázaných minorů či podrozdělení je znám pouze u jediné vyšší plochy. Petr Hliněný, FI MU Brno 5 FI: MA010: Kreslení grafů Věta 11.6. (Archdeacon) Graf G je nakreslitelný do projektivní roviny právě když neobsahuje žádný z následujících 35 grafů isomorfní svému minoru. Petr Hliněný, FI MU Brno 6 FI: MA010: Kreslení grafů 11.2 O problému rovinného pokrytí Následující zajímavý partikulární problém je hezký především svou "chytlavostí"a jednoduchostí zadání. Je znám pod názvem Negamiho hypotéza planárních pokrytí nebo Negamiho 12 hypotéza. Definice: Říkáme, že graf H pokrývá graf G, pokud existuje surjektivní zobrazení : V (H) V (G) takové, že sousedé každého vrcholu v grafu H jsou bijektivně zobrazeny na sousedy vrcholu (v) grafu G. 2 Hypotéza 11.7. Souvislý graf G má pokrytí (nějakým) konečným rovinným grafem, právě když G samotný je nakreslitelný do projektivní roviny. Zde je příklad dvojitého pokrytí grafu K5 rovinným grafem o 10 vrcholech. 1 2 3 4 5 1 2 3 4 51 2 3 4 5 1 2 3 4 5 + Fakt: Je-li G nakreslitelný do projektivní roviny, pak univerzální pokrytí projektivní roviny sférou okamžitě dá nakreslení dvojitého rovinného pokrytí grafu G. Petr Hliněný, FI MU Brno 7 FI: MA010: Kreslení grafů Lema 11.8. K důkazu Hypotézy 11.7O problému rovinného pokrytítheorem.11.7 stačí ověřit, že žádný z 32 souvislých zakázaných minorů z Věty 11.6Kreslení na určenou plochutheorem.11.6 nemá konečné rovinné pokrytí. Kupodivu pro většinu z oněch 32 grafů to lze dokázat velmi snadno, navíc lze využít následovný poznatek k další výrazné redukci počtu případů: Lema 11.9. Tzv. Y -operace (nahrazení vrcholy stupně 3 trojúhelníkem na jeho sousedech) zachovává konečné rovinné pokrytí. 2 Přesto k této hypotéze stále není znám důkaz (a asi většina matematiků zabývajících se topologickou teorií grafů si s ní už zkoušela někdy lámat hlavu). Nejsilnější publikované poznatky o ní se dají shrnout následovně: Věta 11.10. (Archdeacon, Fellows, Negami, PH) Pokud graf K1,2,2,2 nemá konečné rovinné pokrytí, tak je Hypotéza 11.7O problému rovinného pokrytítheorem.11.7 pravdivá. 2 Věta 11.11. (Thomas, PH) Existuje jen 16 konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.7O problému rovinného pokrytítheorem.11.7 mohla být nepravdivá. Petr Hliněný, FI MU Brno 8 FI: MA010: Kreslení grafů 11.3 Praktické "pružinové" kreslení grafů Závěrem se podívejme na trochu jinou problematiku ­ jak prakticky nakreslit daný (nerovinný) graf, aby to "vypadalo hezky". Fakt: Psychologické výzkumy ukázaly, že jedním z nejvýznamnějších kvantitativních parametrů nakreslení grafu pro jeho "lidskou čitelnost" je počet křížení hran. Tento poznatek na jednu stranu ukazuje důležitost průsečíkového čísla grafu pro jeho vizualizaci, ale na druhou stranu nás nechává v poměrně beznadějné situaci, neboť určení průsečíkového čísla se ukazuje jako prakticky nemožné. Petr Hliněný, FI MU Brno 9 FI: MA010: Kreslení grafů Jeden z nejstarších užitečných heuristických přístupů ke kreslení grafů se dá shrnout následovně: Metoda 11.12. Pružinové kreslení grafu * Vytvoříme "fyzikální" model grafu, kde vrcholy budou kuličkami, které se vzájemně odpuzují, a hrany budou pružinami, které své koncové vrcholy vzájemně přitahují. 2 * Náš model budeme iterovat jako dynamický systém, až do konvergence pozic vrcholů. Zde je potřebné modelovat i "tlumení" pohybů vrcholů, aby nedošlo k rozkmitání systému. 2 * I když kreslíme graf do roviny, je užitečné začít modelovat systém s dimenzí navíc (aby měly vrcholy více "místa k pohybu") a teprve v průběhu času dodatečnou silou přidanou dimenzi "eliminovat", neboli zkonvergovat pozice vrcholů do zvolené roviny.