9   Povídání o průnikových grafech
Od této lekce teorie grafů se zlehka zaměříme 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. Naší 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ší často studované třídy průnikových grafů.
• Reprezentace grafů křivkami a úsečkami.
9.1   Průnikové a intervalové grafy
Definice 9.1. Průnikovým grafem množinového systému M
nazveme graf Im na vrcn- V — M s množinou hran E — {{A, B} C M. : AC\B ^ 0}.
Poznamenáváme také, že nejčastěji studované typy průnikových grafů mají „geometrickou povahu", tj. jejich množiny jsou definovány jako geometrické objekty. □
Fakt: Třídy průnikových grafů jsou vždy uzavřené na indukované podgrafy. □
Tvrzení 9.2. Každý jednoduchý graf je isomorfní průnikovému grafu nějakého vhodného systému množin.
Intervalové grafy
Z celého spektra možných typů průnikových grafů se blíže podíváme na průnikové grafy intervalů na přímce - intervalové grafy (zkratka INT).
Vzpomeňte si, že s intervalovými grafy jsme se vlastně setkali už v Problému 6.5 řešícím přidělení pracovních úkolů, tj. barvení příslušného intervalového grafu. □
Lema 9.3. Každá kružnice délky větší než tři v intervalovém grafu má chordu, tj. indukuje hranu spojující nesousední vrcholy kružnice.
Věta 9.4. Třídu všech intervalových grafů lze charakterizovat pomocínásl. tvrzení. □
• Graf je intervalový právě když neobsahuje žádný z následujících zakázaných indukovaných podgrafů:
Ln;n>l Bj B2
• Jednoduchý graf je intervalový, právě když neobsahuje indukovanou kružnici C4 a jeho doplněk má tranzitivní orientaci.
9.2   Chordální grafy
Definice 9.5. Chordální graf (také zván triangulovaný) G je takový, který neobsahuje indukovanou kružnici delší než tři jako svůj podgraf.
Věta 9.6. 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.
1. Pro každou kružnici C a hranu e v chordálním grafu G existuje hrana / taková, že E{C) \ {e} U {/} obsahuje trojúhelník.
2. Nechť uv je hranou G a No(v), tj. sousedé v, tvoří bisimpliciální podgraf v G. Pokud v je simpliciální mezi sousedy u, ale ne v celém G, pak existuje vrchol w spojený s f a nespojený s u takový, že w je simpliciální mezi sousedy v.
3. Tudíž 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.
4. Tudíž G je bisimpliciální.
Xq — u
Simpliciální dekompozice
Přímým důsledkem Věty 9.6 je existence simpliciální dekompozice libovolného chordálního grafu:
Důsledek 9.7. Vrcholy každého chordálního grafu G lze seřadit do posloupnosti vi, t>2,..., vn tak, že každé Vi, í — 2,..., n, je simpliciální v podgrafu G indukovaném na {vi,.. .,ví-i}.
Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů.
Průniková reprezentace
Věta 9.8. Graf G je chordální právě když existuje strom T takový, že G je průnikovým grafem vhodné kolekce podstromů v T. □
Důkaz (náznak): Ve směru doleva pouze stručně konstatujeme, že každý průnikový graf podstromů v nějakém stromě nutně musí být chordální. Naopak povedeme důkaz indukcí podle počtu vrcholů G, přičemž báze pro jeden vrchol je zřejmá.
Jinak nechť f 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 se v 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. C
9.3   Další třídy průnikových grafů
Definice: Zavedeme následující třídy průnikových grafů:
• Hranový graf L(G) je průnikovým grafem hran E(G) v běžném grafu G.
• Kruhově-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.
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.
Složitost rozpoznávání
Častou a důležitou otázkou u (jakýchkoliv) typů reprezentací grafů je, které abstraktní grafy mají reprezentaci daného typu a jak lze takovou reprezentaci algoritmicky sestrojit. Problému se říká rozpoznávání daného typu grafů. □
Věta 9.9. Hranové, CA a CIR grafy lze rozpoznávat algoritmy v polynomiálním čase. Problém, zda daný abstraktní graf je DISC nebo BOX je NP-úplné. □
Věta 9.10. Daný graf je hranovým grafem nějakého jednoduchého grafu, právě když neobsahuje žádný z následujících indukovaných podgrafů:
Jiné druhy reprezentace
• 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.11. Graf je rovinný právě když je dotykovým grafem kruhů v rovině.
• Obdélníkové „duály" - to jsou průnikové dotykové reprezentace grafu pomocí nepřekrývajících se obdélníků se stranami rovnoběžnými osám.
- V této reprezentaci není dovoleno setkání čtyř obdélníků v jednom rohu. □
- Ve striktním podání musí obdélníky reprezentace vyplnit plochu „bez děr".□
Fakt: Pouze rovinné grafy mohou mít obdélníkový duál, avšak ne všechny rovinné grafy je mají.n
Navíc striktní obdélníkové duály vždy reprezentují kvazitriangulace (všechny stěny až na vnější jsou trojúhelníky).
9.4   Průnikové grafy křivek a úseček
Definice: Niiovými grafy nazveme průnikové grafy (obyčejných) křivek v rovině. Tvrzení 9.12. Každý rovinný graf je nitový.
Tvrzení 9.13. Existují grafy, které jsou nitové, 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.13 je mnohem obtížnější dokázat příslušnost problému do třídy MV, než jeho těžkost, [Kratochvíl / Pelsmajer, Schaeffer, Stefankovič].
Věta 9.14. Problém rozpoznat, zda daný graf je niíový, je MV-úplný. □
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.15. 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.16. 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.17. 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. □
Opět se jedná o výpočetně obtížnou třídu grafů, nebot již:
Věta 9.18. Problém rozpoznat dotykový graf úseček je MV-úplný.