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? Ukážeme si dva různé pohledy. Jednak 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í, d Stručný přehled lekce • 0 „vyšších" plochách, orientovatelné a neorientovatelné plochy. • Kreslení grafů na plochy, popis nakreslení, Eulerův vztah. • Grafy na plochách a zakázané minory. • Průsečíkové číslo grafu, základní definice a fakta. • Zlehka o kuriózním problému rovinného pokrytí. Petr Hliněný, Fl MU Brno 1 Fl: MAOIO: Kreslení grafů 11.1 Co jsou to 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 bez hranice) je homeomorfní - S0 sféře, - S h 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ří). Přidávání uší na sféru je snadno představitelná konstrukce, viz ilustrace nalevo. Avšak crosscap je velmi obtížné vizualizovat v Euklidovské geometrii, takže pro ilustraci si jej (téměř ekvivalentně) můžeme nahradit připojováním Möbiova proužku - viz ilustrace napravo, k hranici polosféry. Petr Hliněný, Fl MU Brno ______________________________________________: MA010: Kreslení grafů Fakt: Plocha 2 crosscapu a h uší, tak S je homeomorfní ploše vzniklé ze sféry přidáním k — 2 crosscapu a h + 1 uší. etr Hliněný, Fl MU Brno Fl: MA010: Kreslení grafů 11.2 Kreslení grafů na plochy 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. d 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. 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 u stěn.)c 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".) Rotační schéma u každého vrcholu v nakreslení určuje cyklické pořadí hran (v globálně zvolené orientaci) vycházejících z tohoto vrcholu v našem nakreslení. Petr Hliněný, Fl MU Brno 4 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 Ke, na torus i K-j, kdežto na Kleinovu láhev také jen Ke- Mnohé poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Z těch jednoduchých je nejdůležitější Eulerův vztah (Věta 8.2). Věta 11.6. Nechť buňkové nakreslení souvislého grafu G na ploše E má f stěn. Pak \V(G)\ + f-\E(G)\ = x&)., kde x(E) (Eulerova charakteristika plochy) je 2 — 2h pro E = Sh a 2 —k pro E = J\ígj Z Eulerova vztahu vyplývají důležitá omezení na maximální počet hran -jednoduchý n-vrcholový graf nakreslený na toru nebo Kleinově láhvi nemůže mít více než 3n hran. ________etr Hliněný, Fl MU Brr___________________________________________________I: MA010: Kreslení grafů ľ 11.3 Překážky kreslení na plochy Podle Věty 8.5 lze rovinnost zadaného grafu poměrně rychle algoritmicky rozhodnout i najít nakreslení. I tento silný výsledek má stejně silné zobecnění na vyšší plochy, ale už bohužel není vhodný pro praktické implementace. Věta 11.7. (Mohär) Pro každou pevnou plochu E existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na E, nebo určí minimální překážku na křesl itelnosti na E. □ Poznámka: Za poznamenání stojí, že obecnější problém určit nejjednodušší plochu, na kterou lze daný graf nakreslit, je už A/'P-tež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í známe pouze u jediné vyšší plochy. V etr Hliněný, Fl MU Brno FhMAOlO: Kreslení grafů Věta 11.8. (Archdeacon) Graf G je nakreslitelný do projektivní roviny právě když neobsahuje žádný minor isomorfní některému z následujících 35 grafů. «» Detr Hliněný, Fl MU Brno FhMAOlO: 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. • 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 nakreslitelny 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 iso-morfní H, má stromovou dekompozici (Definice 10.4) takovou, jejíž každý balík indukuje podgraf, který je až na omezeně mnoho „lokálních výjimek" nakreslitelny na nějakou plochu £ takovou, že H na £ nakreslit nelze. Petr Hliněný, Fl MU Brno 8 Fl: MA010: Kreslení grafů 11.4 O průsečíkovém čísle grafů Třebaže již dobře víme (a umíme algoritmicky rozpoznat), které grafy jsou rovinné, praxe požaduje „hezká nakreslení v rovině" i pro nerovinné grafy. Jak tedy na hezká kreslení nerovinných grafů do roviny? c Definice (rozšíření Definice 8.1): Nakreslením grafu G do roviny rozumíme zobrazení, ve kterém jsou vrcholům G přiřazeny různé body roviny a hranám jednoduché křivky spojující koncové vrcholy. Přitom je požadováno, aby se žádné tři hrany neprotínaly v jednom bodě (jiném než koncový vrchol), aby žádná hrana neprocházela jiným vrcholem a aby se každá protínající dvojice hran skutečně „křížila" (tj. ne jednostranný dotyk). Příklad 11.10. Podívejme se na následující tři (korektní) nakreslení do roviny. Jsou všechna „optimální", tj. je počet jejich křížení nejmenší možný? Snadno vidíme, že první graf lze nakreslit i bez křížení a druhý graf jen s jedním křížením. Naopak třetí graf už s méně kříženími nakreslit nelze. Uměli byste toto dokázat? Ü Petr Hliněný, Fl MU Brnc________________________________________________Fl: MA010: Kreslení grafů Definice 11.11. Průsečíkové číslo grafu G v rovině je definováno jako nejmenší možný počet křížení dvojic hran přes všechna korektní nakreslení G do roviny. Značíme cr(G). Původ problému průsečíkového čísla spadá do doby druhé světové války, kdy P. Turán byl na nucených pracech v cihelně. Jejich úkolem bylo tlačit vozíky s cihlami po kolejnicích a na každé křižovatce s tím měli velké problémy. Proto Turán přemýšlel, jak navrhnout kolejiště lépe, aby minimalizoval počet křížení kolejnic. V dnešní době je problém průsečíkového čísla velmi důležitý v praktických oblastech VLSI designu [Leighton] a „lidsky čitelné" vizualizace grafů v různých schématech. etr Hliněný, Fl MU Brno 10 Fl: MA010: Kreslení Příklad 11.12. Určeme průsečíková čísla následujících dvou grafů: Asi snadno každý nalezne nakreslení prvního grafu (Petersenův) s pouze dvěma kříženími hran. Jak však dokázat, že jej nelze nakreslit s jedním křížením? Všimněme si, že každá jeho hrana je „ekvivalentní" s každou jinou. To znamená, že by ostraněním jedné zvolené hrany z Petersenova grafu mělo vytvořit rovinný graf, ale to není pravda. Druhý graf Kq lze nakreslit s 3 kříženími - začněme s kružnicí délky 5 a posledním vrcholem spojeným uvnitř. Zbylých 5 hran pak už dokážeme dokreslit s vytvořením tří křížení. Zkuste si to! Proč není možných méně křížení? Předpokládejme, že dvě křížení hran postačují, pak bychom vypuštěním dvou dotčených hran získali rovinný graf. Ten by však měl 6 vrcholů a 13 > 3 • 6 — 6 hran, spor. D etr Hliněný, Fl MU Bn Fl: MA010: Kreslení Fakt: Přesné obecné hodnoty průsečíkových čísel nejsou známy ani pro úplné či úplné bipartitní grafy, d Věta 11.13. Problém určit, zda průsečíkové číslo cr(G) < k pro G a k na vstupu je MV-úplný. Toto platí dokonce i když G je kubický 3-souws/ý graf. Zamyslete se sami, proč by problém průsečíkového čísla měl vůbec náležet do třídy AfV, není to tak zřejmé.. . d V praxi se ukazuje, že určení průsečíkového čísla je přímo zoufale těžký problém, ještě mnohem beznadějnější než třeba barevnost. Snad jediným existujícím „pozitivním" (i když zcela nepraktickým) algoritmickým výsledkem je následující: Věta 11.14. Pro fixní k lze otestovat, zda cr(G) < k, v lineárním čase vzhledem k počtu vrcholů grafu (závislost na parametru k je však doslova „ brutální"), a Aby nebylo všem špatným zprávám konec, v roce 2010 Cabello a Mohar dokázali následující velmi překvapivý výsledek. Věta 11.15. Je-li dán rovinný graf G a dvojice jeho nespojených vrcholů u,v, tak problém určit, zda průsečíkové číslo cr(G + uv) < k pro k na vstupu je MV-úplný. Petr Hliněný, Fl MU Brno 12 Fl: MA010: Kreslení grafů 11.5 O problému rovinného pokrytí Na závěr si jako kuriozitu uvedeme zajímavý, třebaže okrajový, problém známý od 80-tých let pod názvem Negamiho hypotéza planárních pokrytí nebo Negamiho 12 oc hypotéza. Avšak k velmi podobné otázce nezávisle ve stejné době dospěl i Fellows. Problém je hezký především svou „chytlavostí" a jednoduchostí zadání. 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 etr Hliněný, Fl MU Bn Fl: MA010: Kreslení grafů Negamiho hypotéza rovinných pokrytí Hypotéza 11.16. 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 Ks rovinným grafem o 10 vrcholech. t(vi) = T (v 2) = 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. V^ Petr Hli něný, Fl MU Bn Fl: MA010: Kreslení grafů Letna 11.17. K důkazu Hypotézy 11.16 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. Další výsledky na kterých se podíleli Archdeacon, Fellows, Negami, Thomas a autor, vedly k dále uvedeným poznatkům, které jsou tím nejsilnějším, co o řešení Negamiho hypotézy víme. Věta 11.18. Pokud graf Ki2,2,2 nemá kon. rov. pokrytí, je Hypotéza 11.16 pravdivá. Věta 11.19. Existuje jen 16 následujících konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.16 mohla být nepravdivá. etr Hliněný, Fl MU Bn Fl: MA010: Kreslení O rovinných emulátorech Mírnou modifikací konceptu planárního pokrytí představuje tato definice, podaná Fel-lowsem 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 surjek-tivně 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 etr Hliněný, Fl MU Bn Fl: 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.20. (Rieck a Yamashita) Existuje graf, který není projektivní a nemá konečné rovinné pokrytí a přesto má konečný rovinný emulátor. Problematika, které grafy mají konečné rovinné emulátory, je stále široce otevřená. ;tr Hliněný, Fl IV Fl: MAOIO: Kreslení grafů