9 Krátké povídání o průnikových grafech Od této lekce teorie grafů se zaměříme lehce na několik vybraných partií teorie grafů blízkých autorovu srdci. . . Naším prvním výběrem jsou průnikové grafy, což jsou grafy, jejichž vrcholy jsou jisté množiny a hrany spojují pronikající se dvojice. Pochopitelně hlavní motivací studia těchto grafů je jejich geometrická názornost a aplikovatelnost v reálných situacích. Stručný přehled lekce • Co jsou průnikové grafy, příklad intervalových grafů. • Chordální grafy a jejich vlastnosti. • Některé další třídy průnikových grafů. • Reprezentace grafů křivkami a úsečkami. 'etr Hliněný, Fl IV Fl: MAOIO: Průnikové grafy 9.1 Průnikové a intervalové grafy Definice 9.1. Průnikovým grafem množinového systému M nazveme graf Ij^ na vrch. V = A4 s množinou hran E = {{A, B} C A4 : AC\B ^ Fakt: Průnikové grafy (určitého typu) jsou vždy uzavřené na indukované podgrafy. Fakt: Každýjednoduchýgraf je isomorfní průnikovému grafu nějakého systému množin. Stačí zvolit soubor hran incidentních s vrcholem x za množinu Mx reprezentujícím. etr Hliněný, Fl MU Br Fl: MA010: Průnikové grafy Intervalové grafy Pro začátek se podívejme na průnikové grafy intervalů na přímce - intervalové grafy (zkratka INT). 1 2 •-----------5= 4 5 3 . - Vzpomeňte si, že s intervalovými grafy jsme se vlastně setkali už v Problému 5.5. Letna 9.2. Každá kružnice délky větší než tři v intervalovém grafu má chordu. Detr Hliněný, Fl MU Br Fl: MA010: Průnikové grafy Věta 9.3. Třídu všech intervalových grafů lze charakterizovat pomocí násl. tvrzení, a • Graf je intervalový právě když neobsahuje žádný z následujících zakázaných indukovaných podgrafů: C„;n>4 1 2 1 2 3- n Kn,n>2 L „;n>l • Graf je intervalový, právě když neobsahuje indukovanou kružnici C4 a jeho doplněk má tranzitivní orientaci. ___________________________________________zl: MAOIO: Průnikové grafy ^ -*etr Hlinený, H MU Brr 9.2 Chordální grafy Definice: Graf G je chordální pokud neobsahuje indukovanou kružnici delší než tři. Například: Věta 9.4. Každý chordální graf G obsahuje simpliciálnívrchol, tj. vrchol s takový, že všichni sousedé s tvoří kliku v G. □ Důkaz: Dokazujeme posloupnost tří snadných tvrzení o chordálním grafu G. Řekneme, že graf H je bisimpliciální, pokud H je úplný nebo H obsahuje dva nespojené simpliciální vrcholy. etr Hliněný, Fl MU Br Fl: MA010: Průnikové grafy Pro každou kružnici C a hranu e v G existuje hrana / taková, že C\ {e} U {/} obsahuje trojúhelník, d Nechť uv je hranou G a sousedé v tvoří (indukují) bisimpliciální podgraf. Pokud v je simpliciální mezi sousedy u, ale ne v celém G, pak existuje vrchol w spojený s -y a nespojený s u takový, že w je simpliciální mezi sousedy v. Pokud G není bisimpliciální, ale sousedé každého jeho vrcholu indukují bisimpliciální podgraf, pak G obsahuje kružnici C odporující bodu 1. Tudíž G je bisimpliciální. xq = u D etr Hliněný, Fl MU Br Fl: MA010: Průnikové grafy r Přímým důsledkem Věty 9.4 je existence simpliciální dekompozice libovolného chordálního grafu; jedná se o seřazení jeho vrcholů do posloupnosti vi,V2, ■ ■ ■,vn tak, že každé ví, i = 2,..., n, je simpliciální v podgrafu indukovaném na ví,..., Vi-\. Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. Věta 9.5. Graf G je chordální právě když G je průnikovým grafem podstromů ve vhodném stromě. : Důkaz (náznak ve směru doprava): Povedeme indukcí podle počtu vrcholů G. Báze pro jeden vrchol je zřejmá. Navíc zřejmě každý průnikový graf podstromů v nějakém stromě musí být chordální. Jinak nechť v je simpliciální vrchol chordálního grafu G. Indukcí sestrojíme průnikovou reprezentaci také chordálního grafu G — v. Pak sousedé v tvoří kliku, tudíž v průnikové reprezentaci grafu G — v sev některém uzlu stromu všichni překrývají. Na tomto místě přidáme nový list stromu, který bude reprezentovat v a bude překryt reprezentanty sousedů v. ü etr Hliněný, Fl MU_____________________________________________________MA010: Průnikové grafy 9.3 Třídy průnikových grafů Zde si uvedeme jen stručný neformální přehled některých typů průnikových grafů, které jsou běžně studovány. • Hranový graf je průnikovým grafem hran v běžném grafu. • Kru hově-intervalové grafy (CA) jsou průnikovými grafy intervalů na kružnici. • Kružnicové grafy (CIR) jsou průnikovými grafy tětiv v kružnici. Pa C5 P4 **% ^etr Hliněný, Fl MU Brno I: MA010: Průnikové grafy • Diskové grafy (DISC) jsou průnikovými grafy kruhů v rovině. Lze uvažovat také jen jednotkové kruhy (unit-DISC). • Kvádrové grafy (BOX) jsou průnikovými grafy kvádrů ve dvou, třech či více dimenzích, se stěnami rovnoběžnými se souřadnicemi. etr Hliněný, Fl MU Br Fl: MA010: Průnikové grafy • Dotykové .. . grafy jsou variantou průnikových grafů geometrických objektů, ve které se požaduje, aby vnitřky objektů byly po dvou disjunktní. Věta 9.6. (Koebe) Graf je rovinný právě když je dotykovým grafem kruhů v rovině.a • Jiné, tzv. viditelnostní grafy nejsou definovány průniky objektů, ale jejich vzájemnou viditelností v geometrickém světě. Použití nacházejí například při plánování cesty autonomního robota. etr Hliněný, Fl MU Bn rtAO^^Pmnikov^n^fy 9.4 Průnikové grafy křivek a úseček Definice: Hitovými grafy nazveme průnikové grafy (obyčejných) křivek v rovině. Tvrzení 9.7. Každý rovinný graf je niiový. □ Tvrzení 9.8. Existují grafy, které jsou niiové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálně mnoho vzájemných průsečíků. Co se týče algoritmické složitosti, je poznání niťových grafů velmi algoritmicky náročné. Vhledem k Tvrzení9.8 je mnohem obtížnější dokázat příslušnost problému do třídy J\ÍV, než jeho těžkost, [Kratochvíl / Pelsmajer, Schaeffer, Stefankovič]. Věta 9.9. Problém rozpoznat, zda daný graf je niiový, je MV-úplný, c Velmi podobně je definována třída úsečkových grafů, což jsou průnikové grafy úseček v rovině. Opět je dokázáno, že jejich rozpoznávání je TVP-těžké [Kratochvíl], ale příslušnost problému do třídy MV zůstává otevřená kvůli následujícímu. Tvrzení 9.10. Existují grafy, které jsou úsečkové, ale každá jejich taková reprezentace obsahuje úsečku, k zápisu jejíž souřadnic je třeba exponenciálně mnoho bitů. Hypotéza 9.11. Je každý rovinný graf úsečkovým grafem? „Zápalkové" grafy Výše jsem zmínili obecný pojem geometrických dotykových grafů, nyní se z tohoto úhlu pohledu podíváme na dotykové grafy úseček v rovině: Tímto pojmem nazýváme ty průnikové grafy úseček v rovině, u nichž je dodatečnou podmínkou, že žádné dvě úsečky se neprotínají ve svých vnitřních bodech. (Jakoby „zápalkové" reprezentace v rovině.) Věta 9.12. Graf je dotykovým grafem disjunktních horizontálních a disjunktních vertikálních úseček, právě když se jedná o rovinný bipartitnígraf a Opět se jedná o výpočetně obtížnou třídu grafů, neboť již: Věta 9.13. Problém rozpoznat dotykový grafúseček je J\ÍV'-úplný. □ _________■ Hliněný, Fl MU Brn< \010: Průnikové grafy