Petr Hliněný, FI MU Brno 1 FI: MA010: Průnikové grafy
9 Krátce 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.
s ss s s ss s s ss s
1 2 3 4 5
6
2
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.
Petr Hliněný, FI MU Brno 2 FI: MA010: Průnikové grafy
9.1 Intervalové a chordální grafy
Definice 9.1. Průnikovým grafem množinového systému M
nazveme graf IM na vrch. V = M s množinou hran E = {A, B  M : A  B = }.
2
Intervalové grafy
Podívejme se na průnikové grafy intervalů na přímce ­ intervalové grafy (zkratka INT).
s ss s s ss s s ss s
1 2 3
4 5
6
ss
s
s
s
s
1 2
3
4
5 6
2
Fakt: Každá kružnice délky větší než tři v intervalovém grafu má chordu.
Petr Hliněný, FI MU Brno 3 FI: MA010: Průnikové grafy
* Intervalové grafy lze popsat následujícícmi zakázanými indukovanými podgrafy:
2
* Graf je intervalový, právě když neobsahuje indukovanou C4 a jeho doplněk má
tranzitivní orientaci. 2
* Jednotkové intervalové grafy jsou ty mající intervalovou reprezentaci se všemi
intervaly délky 1. Jsou to právě ty intervalové grafy bez indukovaného K1,3.
Petr Hliněný, FI MU Brno 4 FI: MA010: Průnikové grafy
Chordální grafy
Definice: Graf G je chordální pokud neobsahuje indukovanou kružnici delší než tři. 2
Věta 9.2. Každý chordální graf G obsahuje simpliciální vrchol, tj. vrchol s takový, že
všichni sousedé s tvoří kliku v G. 2
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.
Petr Hliněný, FI MU Brno 5 FI: MA010: Průnikové grafy
1. Pro každou kružnici C a hranu e v G existuje hrana f taková, že C \ {e}  {f}
obsahuje trojúhelník. 2
2. 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 v a nespojený s u takový, že w je simpliciální mezi sousedy v.
3. 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í.
x0 = u
NG(x0)
x1 = v
x2 = w
NG(x1)
x3
x-1
x-2
NG(x-1)
x-3
2
Petr Hliněný, FI MU Brno 6 FI: MA010: Průnikové grafy
Přímým důsledkem Věty 9.2 je existence simpliciální dekompozice libovolného chordálního
grafu; jedná se o seřazení jeho vrcholů do posloupnosti v1, v2, . . . , vn tak, že každé
vi, i = 2, . . . , n, je simpliciální v podgrafu indukovaném na v1, . . . , vi-1.
Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i
chordálních grafů. 2
Věta 9.3. Graf G je chordální právě když G je průnikovým grafem podstromů ve
vhodném stromě. 2
Důkaz (náznak): 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 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. 2
Petr Hliněný, FI MU Brno 7 FI: MA010: Průnikové grafy
9.2 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. 2
* Kruhově-intervalové grafy (CA) jsou průnikovými grafy intervalů na kružnici. 2
* Kružnicové grafy (CIR) jsou průnikovými grafy tětiv v kružnici. 2
* Diskové grafy (DISC) jsou průnikovými grafy kruhů v rovině. Lze uvažovat také
jen jednotkové kruhy (unit-DISC). 2
* 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. 2
* 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.4. Graf je rovinný právě když je dotykovým grafem kruhů v rovině. 2
* Jiné, tzv. viditelnostní grafy nejsou definovány průniky objektů, ale jejich vzájemnou
viditelností v geometrickém světě.
Petr Hliněný, FI MU Brno 8 FI: MA010: Průnikové grafy
9.3 Průnikové grafy křivek a úseček
Definice: Niťovými grafy nazveme průnikové grafy (obyčejných) křivek v rovině.
Tvrzení 9.5. Každý rovinný graf je niťový. 2
Tvrzení 9.6. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace
obsahuje dvojici křivek majících exponenciálně mnoho vzájemných průsečíků. 2
Co se týče algoritmické složitosti, je poznání niťových grafů velmi algoritmicky náročné.
Vhledem k Tvrzení 9.6 je mnohem obtížnější dokázat příslušnost problému do třídy NP,
než jeho těžkost, [Kratochvíl / Pelsmajer, Schaeffer, Štefankovič].
Věta 9.7. Problém rozpoznat, zda daný graf je niťový, je NP-úplný. 2
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 NP-těžké [Kratochvíl], ale
příslušnost problému do třídy NP zůstává otevřená kvůli následujícímu.
Tvrzení 9.8. 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ů. 2
Hypotéza 9.9. Je každý rovinný graf úsečkovým grafem?
Petr Hliněný, FI MU Brno 9 FI: MA010: Průnikové grafy
,,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.10. 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. 2
Opět se jedná o výpočetně obtížnou třídu grafů [PH].
Věta 9.11. Problém rozpoznat dotykový graf úseček je NP-úplný. 2
U ,,zápalkových grafů je možno dále zkoumat několik dodatečných omezení.
­ Povolíme ,,oboustranné dotyky úseček, nebo jen jednostranné? 2
­ Kolika úsečkám dovolíme dotyk v jednom bodě?  k-dotykové grafy 2
­ Co když zobecníme úsečky na obyčejné křivky v rovině?
Dá se ukázat, že třídy dotykových grafů popsané předchozími body jsou různé a obtížnost
jejich rozpoznání zůstává, až na triviální případy. . .