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. 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í. Zde už se jedná o vyloženě aplikovaný počítačový problém. . . 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 (vnitřek kruhu přitom ploše už nepatří). 2 Poznámka: Plocha S1 je známý torus, neboli povrch duše kola. 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 (bez své hranice!) 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 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 K6, na torus i K7, kdežto na Kleinovu láhev také jen K6. 2 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 má f stěn. Pak |V (G)| + f - |E(G)| = () , kde () (Eulerova charakteristika plochy) je 2-2h pro = Sh a 2-k pro = N k.2 Věta 11.7. (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í máme pouze u jediné vyšší plochy. Petr Hliněný, FI MU Brno 5 FI: 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ý, FI MU Brno 6 FI: MA010: Kreslení grafů Význam grafů na plochách 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. 2 * 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. 2 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 takovou, že H na nakreslit nelze. Petr Hliněný, FI MU Brno 7 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. 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í : 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.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. 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 8 FI: MA010: Kreslení grafů Lema 11.11. K důkazu Hypotézy 11.10 stačí ověřit, že žádný z 32 souvislých zakázaných minorů 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. Y -operace (nahrazení vrcholu stupně 3 trojúhelníkem na jeho sousedech) zachovává vlastnost míti 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.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ý, FI MU Brno 9 FI: 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á. Petr Hliněný, FI MU Brno 10 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 11 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.15. 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.