11 Něco 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. Mimo tradičního kreslení grafů „na papír", tj. do roviny, si lze představit kreslení grafů na složitější povrchy (plochy), třeba na povrch duše pneumatiky. Co nám takovéto rozšířené kreslení grafů přinese nového? Nebo zůstaneme v rovině, ale povolíme křížení hran a budeme hledat „esteticky pěkná" nakreslení, či dokonce jiné modely jako rovinná pokrytí, c 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í. • Nastínění „pružinového algoritmu" pro kreslení grafů do roviny. Petr Hliněný, Fl MU Brno 1 Fl: 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). - N k 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 (vnitřek kruhu přitom ploše už nepatří), c Poznámka: Plocha Si je známý torus, neboli povrch duše kola. Plocha Mi je projektivní rovina a vypuštěním kruhu z Mi vzniká známý Móbiův proužek. Plocha M2 je tzv. Kleinova láhev. □ Plochy S a Sh jsou orientovatelné, kdežto Mk jsou neorientovatelné. Lema 11.2. Máme-li plochu X vzniklou ze sféry přidáním k > 2 crosscapů a h uší, tak S je homeomorfní ploše vzniklé ze sféry přidáním k — 2 crosscapů a h+ 1 uší. Petr Hliněný, Fl MU Brno 2 Fl: MA010: Kreslení grafů Definice 11.3. Nakreslení grafu G na plochu E myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body na S 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. c Na vyšší plochy přenášíme i další pojmy rovinného kreslení, jako pojem stěny. Definice: Nakreslení grafu G na plochu X je buňkové, pokud je každá stěna (bez své hranice!) homeomorfní otevřenému disku, c Fakt: Buňkové nakreslení grafu G je jednoznačně určeno svými stěnovými kružnicemi a jako takové definuje i plochu X až na homeomorfismus. (Neboli plochu X lze „slepit" z jednotlivých disků stěn podél společných hran stěnových kružnic.) : Tvrzení 11.4. Buňkové nakreslení grafu G na orientovatelnou plochu X 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ý, Fl MU Brno 3 Fl: MA010: Kreslení grafů Kreslení na určenou plochu První otázkou o kreslení grafů na plochy je, zda dokážeme takto nakreslit i jiné než rovinné grafy. Například úplný graf K5 nelze nakreslit do roviny. Tvrzení 11.5. Do projektivní roviny lze bez křížení hran nakreslit úplný graf Kq, na torus i Ki, kdežto na Kleinovu láhev také jen Kq. d Mnohé poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Věta 11.6. Nechť buňkové nakreslení souvislého grafu G na ploše X má f sten. Pak \V(0)\+f-\E(G)\=xP), kde x(S) (Eulerova charakteristika plochy) je 2 — 2h pro X = S h a 2 — k pro S = Nif. Věta 11.7. (Mohar) Pro každou pevnou plochu X existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na X, nebo určí minimální překážku nakreslitelnosti na T,, a Za poznamenání stojí, že obecnější problém určit nejjednodušší plochu, na kterou lze daný graf nakreslit, je už TVP-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í I seznam zakázaných minorů či podrozdělení máme pouze u jediné vyšší plochy. \^ Petr Hliněný. Fl MU Brno__________________________________________Fl: MA010: Kreslení grafů Věta 11.8. (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ý, Fl MU Brn : MA010: Kreslení grafů Původní motivace výzkumu kreslení grafů na plochy je přirozená - byla to především snaha o řešení problému čtyř barev. Nyní však již máme Větu o čtyřech barvách, takže co dále motivuje výzkum kreslení grafů na vyšší plochy, mimo „pěkných obrázků"? S grafy nakreslenými na vyšších plochách se setkáme ve dvou základních teoretických oblastech: • Algebraické - studium pravidelných „map" na plochách, c • Strukturální grafové - celá Robertson-Seymourova teorie grafových minorů, třebaže na první pohled s kreslením grafů nemá nic společného, stojí na grafech nakreslených na plochách, c Abychom poslední překvapivé tvrzení blíže vysvětlili, uvedeme si stručně asi nejdůležitější mezivýsledek Robertson-Seymourovy teorie. (Všimněte si, že minor grafu je vždy nakreslitelný na stejnou plochu jako původní graf, třeba ne buňkově.) Věta 11.9. Mějme nerovinný graf H. Pak každý graf G, který neobsahuje minor isomorfní H, má stromovou dekompozici (Definice 10.1) takovou, jejíž každý balík indukuje podgraf, který je až na omezeně mnoho „lokálních výjimek" nakreslitelný na nějakou plochu X takovou, že H na T, nakreslit nelze. Petr Hliněný, Fl MU Brno 6 Fl: MA010: Kreslení grafů 11.2 O problému rovinného pokrytí Následující zajímavý, třebaže okrajový, 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 12oo hypotéza. Avšak k ekvivalentnímu problému nezávisle ve stejné době dospěl i Fellows. Definice: Říkáme, že graf H pokrývá graf G, pokud existuje surjektivní zobrazení t : V (H) —> V (G) takové, že sousedé každého vrcholu v grafu H jsou bijektivně zobrazeny na sousedy vrcholu t (v) grafu G. G Petr Hliněný, Fl MU Bn : MA010: Kreslení grafů Negamiho hypotéza rovinných pokrytí Hypotéza 11.10. 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. t(vi) = t(v2) = V H V2 Vl G = KB 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ý, Fl MU Bn : MA010: Kreslení grafů r Lema 11.11. K důkazu Hypotézy 11.10 stačí ověřit, že žádný z 32 souvislých zakázaných mi noru z Věty 11.8 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.12. Tzv. YA-operace (nahrazení vrcholu stupně 3 trojúhelníkem na jeho sousedech) zachovává vlastnost míti konečné rovinné pokrytí, □ 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.13. (Archdeacon, Fellows, Negami, PH) Pokud graf K1,2,2,2 nemá konečné rovinné pokrytí, tak je Hypotéza 11.10 pravdivá. Petr Hliněný, Fl MU Brno 9 Fl: MA010: Kreslení grafů Věta 11.14. (Thomas, PH) Existuje jen 16 následujících konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.10 mohla být nepravdivá. Jetr Hliněný, Fl MU Bn : MA010: Kreslení grafů O rovinných emulátorech Mírnou modifikací konceptu planárního pokrytí představuje tato definice, podaná Fellowsem nezávisle na Negamim. Definice: Říkáme, že graf H je emulátorem grafu G, pokud existuje surjektivní zobrazení t : V (H) —> V (G) takové, že sousedé každého vrcholu v grafu H jsou surjektivně zobrazeny na sousedy vrcholu t (v) grafu G. □ Na rozdíl od rovinných pokrytí mohou mít emulátory poměrně bohatší strukturu, přesněji řečeno sousedé mohou být "duplikováni", viz tento příklad emulátoru trojúhelníka: C2 b2 H G 3etr Hliněný, Fl MU Bn : MA010: Kreslení grafů Jelikož je na první pohled z definice "jasné", že duplikace sousedů nemůže být přínosná pro existenci planárních emulátorů (ve srovnání s pokrytími), již Fellows vyslovil domněnku, že souvislý graf má konečné rovinné pokrytí právě tehdy, když má konečný rovinný emulátor. Přesto se na závěr roku 2008 objevilo skutečné překvapení: Věta 11.15. (Rieck and Yamashita 2008) Existuje graf, který není projektivní a nemá konečné rovinné pokrytí a přesto má konečný rovinný emulátor. 3 2 Problematika, které grafy mají konečné rovinné emulátory, je stále široce otevřená. etr Hliněný. Fl MU Bri : 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é. etr Hliněný. Fl MU Brn 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.16. 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í. • 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, d • 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. etr Hliněný, Fl MU Brno 14 Fl: MA010: Kreslení grafů