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í 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: Mějme množinový systém M. Jeho průnikovým grafem nazveme graf IM
na vrcholech V = M s množinou hran E = {A, B  M : A  B = }. 2
Intervalové grafy
Jedná se o průnikové grafy intervalů na přímce (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:
* Graf je intervalový, právě když neobsahuje indukovanou C4 a jeho doplněk má
tranzitivní orientaci.
* 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 žádnou indukovanou kružnici delší než
tři. 2
Věta 9.1. 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. 2
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. 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í.
2
Petr Hliněný, FI MU Brno 5 FI: MA010: Průnikové grafy
x0 = u
NG(x0)
x1 = v
x2 = w
NG(x1)
x3
x-1
x-2
NG(x-1)
x-3 2
Simpliciální dekompozice.. . (postupně odebíráme simpliciální vrcholy)
Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i
chordálních grafů. 2
Věta 9.2. Graf G je chordální právě když G je průnikovým grafem podstromů v nějakém
stromě.
Důkaz indukcí podle počtu vrcholů ­ odebíráme simpliciální.. . 2
Petr Hliněný, FI MU Brno 6 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 studovány.
* Hranový graf je průnikovým grafem hran v běžném grafu.
* 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.
* 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.3. Graf je rovinný právě když je dotykovým grafem kruhů v rovině.
* 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 7 FI: MA010: Průnikové grafy
9.3 Průnikové grafy křivek a úseček
Niťovými grafy krátce nazveme průnikové grafy křivek v rovině.
Tvrzení 9.4. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace
obsahuje dvojici křivek majících exponenciálně mnoho (k počtu vrcholů) vzájemných
průsečíků. 2
Není tedy divu, že v následující větě bylo tou mnohem obtížnější částí dokázat příslušnost
problému do třídy NP [Kratochvíl + Pelsmajer, Schaeffer, Štefankovič].
Věta 9.5. Problém poznat, zda daný graf je niťový, je NP-úplný. 2
Velmi podobně je definována třída segmentový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é, ale příslušnost
problému do třídy NP je tentokrát otevřená kvůli následujícímu:
Tvrzení 9.6. Existují grafy, které jsou segmentové, ale každá jejich taková reprezentace
obsahuje úsečku, k zápisu jejíž souřadnic je třeba exponenciálně mnoho (k počtu
vrcholů) bitů. 2
Hypotéza 9.7. Je každý rovinný graf segmentovým grafem?
Petr Hliněný, FI MU Brno 8 FI: MA010: Průnikové grafy
"Zápalkové" grafy
Tímto pojmem nazýváme průnikové grafy úseček v rovině, přičemž dodatečnou podmínkou
je, že žádné dvě úsečky se neprotínají ve svých vnitřních bodech. (Jedná se
tedy o dotykové grafy úseček.)
Věta 9.8. Graf je zápalkovým grafem s horizontálními a vertikálními ,,zápalkami ,
právě když se jedná o rovinný bipartitní graf. 2
Zajímavá podotázka se týká toho, zda povolit ,,dvoustranné dotyky zápalek nebo ne.
.................
Věta 9.9. Problém poznat, zda daný graf je zápalkový, je NP-úplný. 2