9   Krátké povídání o průnikových grafech
Od teto lekce teorie grafů se zaměříme lehce na několik vybraných parti í teorie grafů bl ízkých autorovu srdci. . .
NaSím prvn ím výberem jsou průnikové grafy, coZ jsou grafy, jejichZ vrcholy jsou jiste mnoZiny a hrany spojuj í pronikaj íc í se dvojice. Pochopitelne hlavn í motivac í studia techto grafu je jejich geometricka nazornost a aplikovatelnost v realnych situac ích.
StrůCný přehled lekce
Co jsou průnikové grafy, příklad intervalových grafů.
Chordainí grafy a jejich vlastnosti.
Nékteré dalSí trídy průnikových grafů.
Reprezentace grafů krivkami a ůseCkami.
V
Petr Hliněný,  FI MU Brno
FI: MA010: 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 Im na vrch. V = M s množinou hran E = {{A, B} C M : A n B = 0}.
Fakt: PrUnikové grafy (urCitého typu) jsou vždy uzavřené na indukované podgrafy.
Fakt: Každy jédnoduchy graf jé isomorfní pmnikovému grafu néjakého systému množin. Stačí zvolit soubor hran incidéntních s vrcholém x ža množinu Mx répréžéntující x.
Petr Hliněný,  FI MU Brno
FI: 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 A 5
1 2
•-»5
Vzpomeňte si, ze s intervalovými grafy jsme se vlastně setkali uZ v Problému 5.5.
Lema 9.2. Každá kružnice délky větší než tři v intervalovém grafu ma chordu.
3
5
5
55
5
Petr Hliněný,  FI MU Brno
FI: MA010: Průnikové grafy
Věta 9.3. Třídu všech intervalových grafU lže charakterizovat pomocí nasl. tvrzení. c
• Graf je intervalový prave kdýž neobsahuje žádný ž následujících zakázaných indukovaných podgrafU:
• Graf je intervalový, prave kdýž neobsahuje indukovanou kružnici C4 a jeho doplněk ma tranžitivní orientaci.
Petr Hliněný,  FI MU Brno
FI: MA010: Průnikově grafý
9.2   Chordainí grafy
Definice: Graf G je chordainí pokud neobsahuje indukovanou kružnici delší než tři. Například:
Veta 9.4. Každý chordainí graf G obsahuje simplicialni vrchol, tj. vrchol s takový, že všichni sousede s tvori kliku v G. l
Důkaz: Dokazujeme posloupnost tří snadných tvrzení o chordainím grafu G.
Řekneme, že graf H je bisimplicialni, pokud H je u plný nebo H obsahuje dva nespojene simpliciainí vrcholy.
Petr Hliněný,  FI MU Brno
FI: MA010: Průnikově grafy
5
L
1. Pro každou kružnici C a hranu e v G existuje hrana / taková, že C \ {e} U {/} obsahuje trojUheln ík. c
2. Nechť uv je hranou G a sousede v tvorí (indukuj í) bisimplicialn í podgraf. Pokud v je simplicialn í meži sousedy u, ale ne v celem G, pak existuje vrchol w spojený s v a nespojený s u takový, že w je simplicialn í meži sousedy v.
3. Pokud G nen í bisimplicialn í, ale sousede každeho jeho vrcholu indukuj í bisimplicialn í podgraf, pak G obsahuje kružnici C odporuj íc í bodu 1.
4. Tud íž G je bisimplicialn í.
xo = u
Přímým důsledkem Věty 9.4 je existence simplicialní dekompozice libovolného chordálního grafů; jedna se o seřazení jeho vrcholů do posloupnosti v\, v2,..., vn tak, ze kaZde vj, i = 2,..., n, je simplicialní v podgrafů indůkovanem na vi,..., Vj_i.
Fakt: Simplicialní dekompozici lze výůZít k efektivnímu rozpoznavaní intervalových i chordaln ích grafů. c
Věta 9.5. Graf G je chordálni právě když G je průnikovým grafem podstromu ve vhodném stromě. c
Důkaz (naznak ve smerů doprava): Povedeme indůkcí podle počtů vrcholů G. Baze pro jeden vrchol je zrejma. Navíc zřejme kazdý průnikový graf podstromů v nejakem strome můsí být chordalní.
Jinak necht v je simplicialn í vrchol chordaln ího grafů G. Indůkc í sestroj íme průnikovoů reprezentaci take chordaln ího grafů G — v. Pak soůsede v tvorí kliků, tůd íz v průnikove reprezentaci grafů G — v se v nekterem ůzlů stromů vsichni prekrývaj í. Na tomto m íste přridame nový list stromů, který bůde reprezentovat v a bůde přrekrýt reprezentantý
soůsedů v.
□
V
Petr Hliněný,  FI MU Brno
FI: 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 typu průnikových grafu, ktere jsou bežne studovaný.
• Hranový graf je prunikovým grafem hran v bežnem grafu.
• Kruhově-intervalové grafý (CA) jsou prunikovými grafý intervalu na kružnici.
• Kružnicové grafý (CIR) jsou prunikovými grafý tetiv v kružnici.
• Diskové grafy (DISC) jsou prunikovymi grafy kruhu v roviné. Lžé uvažovat také jén jédnotkové 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.
Petr Hliněný,  FI MU Brno
FI: 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) Grafjé rovinný pravé když jé dotykovým grafém kruhu v rovině.c
• Jine, tžv. viditélnostni grafy nejsou definovany pruniky objektu, ale jejich vžajemnou viditelností v geometrickem svete. Použití nacházejí například pri pianovaní cesty autonomního robota.
Petr Hliněný,  FI MU Brr
FI:MA010: Průnikové grafy
9.4   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.7. Každý rovinný graf je niťový. c
Tvrzen í 9.8. Existují grafy, které jsou nitove, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciélne mnoho vžajemných prUseCíkU. c
Co se týče algoritmicke sloZitosti, je poznaní niťových grafů velmi algoritmicky naročne. Vhledem k Tvrzení9.8 je mnohem obtíZnejSídokazat príslůSnost problemů do trídyMV, neZ jeho tezkost, [Kratochvíl / Pelsmajer, Schaeffer, Stefankovic].
Veta 9.9. Problém rozpoznat, žda daný graf je nitový, je MV-Uplný. c
Velmi podobne je definovana třída úsečkových grafU, coz jsoů průnikove grafy ůsecek v rovine. Opet je dokazano, ze jejich rozpoznavaní je MV-tezke [Kratochvíl], ale příslůsnost problemů do trídy MV zůstava otevřena kvůli nasledůjícímů.
Tvrzen í 9.10. Existujígrafý, ktere jsou úsečkove, ale každa jejich takova reprezentace obsahuje usecku, k žapisu jejíž souřadnic je třeba exponencialne mnoho bitu. c
Hypoteza 9.11. Je kazdy rovinny graf ůseckovym grafem?
Petr Hliněný,  FI MU Brno 11 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ívame na dotýkove grafý usecek v rovine:
Tímto pojmem nazývame ty průnikove grafý úseček v rovine, u nichZ je dodatecnou podm ínkou, Ze zadne dve ůsecký se neprot ínaj í ve svých vnitrn ích bodech. (Jakobý „zapalkove" reprezentace v rovine.)
Věta 9.12. Graf je dotýkovým grafem disjunktn ích horižontaln ích a disjunktn ích ver-tikalních úseček, pravž kdýž se jedna o rovinný bipartitnígraf. c
Opet se jedna o výpocetne obt íznou trídu grafu, neboť ji z:
Věta 9.13. Problem rožpožnat dotýkový graf usecek je MV-uplný.
Petr Hliněný,  FI MU Brr
FI:MA010: Průnikově grafý