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. 1 2 3 4 5_________6 Petr Hliněný, Fl MU Brno Fl: 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. 1 2 3 4 5_________6 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ý, Fl MU Brno Fl: 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 vrcn- V = M s množinou hran E = {A, B G M : AD B ^ 0}. Petr Hliněný, Fl MU Brno Fl: 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 vrcn- V = M s množinou hran E = {A, B G M : AD B ^ 0}. Intervalové grafy Podívejme se na průnikové grafy intervalů na přímce - intervalové grafy (zkratka INT). 1 2 •-----------az 4 5 Petr Hliněný, Fl M MAOIO: 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 vrcn- V = M s množinou hran E = {A, B G M : AD B ^ 0}. Intervalové grafy Podívejme se na průnikové grafy intervalů na přímce - intervalové grafy (zkratka INT). 1 2 •-----------az 4 5 Fakt: Každá kružnice délky větší než tři v intervalovém grafu má chordu. Petr Hliněný, Fl M MAOIO: Průnikové grafy • Intervalové grafy lze popsat následujícícmi zakázanými indukovanými podgrafy: 1 2 3 ■■■ n K -n>2 1 2 ■■■ n L„;n>l Á °4*> Bi Petr Hliněný, Fl Ml Fl: MAOIO: Průnikové grafy • Intervalové grafy lze popsat následujícícmi zakázanými indukovanými podgrafy: 1 2 3 ■■■ n K -n>2 1 2 ■■■ n L„;n>l Á °4*> Bi • Graf je intervalový, právě když neobsahuje indukovanou C4 a jeho doplněk má tranzitivní orientaci. rafy • Intervalové grafy lze popsat následujícícmi zakázanými indukovanými podgrafy: 1 2 L„;n>l 1 2 3 ■■■ n K -n>2 Á °#* Bi • 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 X"i 3. Chordální grafy Definice: Graf G je chordální pokud neobsahuje indukovanou kružnici delší než tři. Petr Hliněný, Fl MU Brno Fl: MA010: Průnikové grafy Chordální grafy Definice: Graf G je chordální pokud neobsahuje indukovanou kružnici delší než tři. 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. Petr Hliněný, Fl MU Brno Fl: MA010: Průnikové grafy Chordální grafy Definice: Graf G je chordální pokud neobsahuje indukovanou kružnici delší než tři. 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. 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ý, Fl MU Brno Fl: MA010: Průnikové grafy 1. Pro každou kružnici C a hranu e v G existuje hrana / taková, že C\ {e} U {/} obsahuje trojúhelník. Petr Hliněný, Fl MU Brno Fl: MAOIO: Průnikové grafy 1. Pro každou kružnici C a hranu e m G existuje hrana / taková, že C\ {e} U {/} 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ý stia 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í. X'o = u 3etr Hliněný, Fl N /lAOlO: Průnikové grafy 1. Pro každou kružnici C a hranu e m G existuje hrana / taková, že C\ {e} U {/} 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ý stia 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í. XQ = U 3etr Hliněný, Fl N /lAOlO: Průnikové grafy Přímým důsledkem Věty 9.2 je existence simpliciálnídekompozice libovolného chordál-ního grafu; jedná se o seřazení jeho vrcholů do posloupnosti v\,V2, ■ ■ ■ ,vn tak, že každé Ví, í = 2,..., n, je simpliciální v podgrafu indukovaném na t»1;..., fj-i- Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. Petr Hliněný, Fl MU Brno Fl: MA010: Průnikové grafy Přímým důsledkem Věty 9.2 je existence simpliciálnídekompozice libovolného chordál-ního grafu; jedná se o seřazení jeho vrcholů do posloupnosti v\,V2, ■ ■ ■ ,vn tak, že každé Ví, í = 2,..., n, je simpliciální v podgrafu indukovaném na t»1;..., fj-i- Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. Věta 9.3. Graf G je chordální právě když G je průnikovým grafem podstromů ve vhodném stromě. Petr Hliněný, Fl MU Brno Fl: MA010: Průnikové grafy Přímým důsledkem Věty 9.2 je existence simpliciálnídekompozice libovolného chordál-ního grafu; jedná se o seřazení jeho vrcholů do posloupnosti v\,V2, ■ ■ ■ ,vn tak, že každé Ví, í = 2,..., n, je simpliciální v podgrafu indukovaném na ví,..., Wj-i. Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. Věta 9.3. Graf G je chordální právě když G je průnikovým grafem podstromů ve vhodném stromě. 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 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. D Petr Hliněný, Fl MU Brno Fl: 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. Petr Hliněný, Fl MU Brno Fl: 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. • Kruhově-intervalové grafy (CA) jsou průnikovými grafy intervalů na kružnici. Petr Hliněný, Fl MU Brno Fl: 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. • 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. 3etr Hliněný, Fl N /lAOlO: 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. • 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). Petr Hliněný, Fl MU Brno Fl: 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. • 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. Petr Hliněný, Fl MU Brno Fl: 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. • 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.4. Graf je rovinný pravé když je dotykovým grafem kruhů v roviné. Petr Hliněný, Fl MU Brno Fl: 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. • 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.4. Graf je rovinný pravé 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ě. 'etr Hlinény, Fl ML Fl: 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ě. Petr Hliněný, Fl MU Brno Fl: 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ý. Tvrzení 9.6. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálne mnoho vzájemných průsečíků. 3etr Hliněný, Fl N /lAOlO: 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ý. Tvrzení 9.6. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálne mnoho vzájemných průsečíků. Co se týče algoritmické složitosti, je poznání niťových grafů velmi obtížné. Vhledem k předchozímu tvrzení je však mnohem obtížnější dokázat příslušnost problému do třídy J\ÍV [Kratochvíl / Pelsmajer, Schaeffer, Štefankovič]. Věta 9.7. Problém rozpoznat, zda daný graf je niťový, je MV-úplný. Petr Hliněný, Fl MU Brno Fl: 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ý. Tvrzení 9.6. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálne mnoho vzájemných průsečíků. Co se týče algoritmické složitosti, je poznání niťových grafů velmi obtížné. Vhledem k předchozímu tvrzení je však mnohem obtížnější dokázat příslušnost problému do třídy J\ÍV [Kratochvíl / Pelsmajer, Schaeffer, Štefankovič]. Věta 9.7. 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 J\ÍV 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álne mnoho bitů. Petr Hliněný, Fl MU Brno Fl: 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ý. Tvrzení 9.6. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálne mnoho vzájemných průsečíků. Co se týče algoritmické složitosti, je poznání niťových grafů velmi obtížné. Vhledem k předchozímu tvrzení je však mnohem obtížnější dokázat příslušnost problému do třídy J\ÍV [Kratochvíl / Pelsmajer, Schaeffer, Štefankovič]. Věta 9.7. 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 J\ÍV 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álne mnoho bitů. Hypotéza 9.9. 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.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. Petr Hliněný, Fl MU Brno Fl: 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. 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 MV-úplný. Petr Hliněný, Fl MU Brno Fl: 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. 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 MV-úplný. 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é? Petr Hliněný, Fl MU Brno Fl: 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. 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 MV-úplný. 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é? - Kolika úsečkám dovolíme dotyk v jednom bodě? —> k-dotykové grafy Petr Hliněný, Fl MU Brno Fl: 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. 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 MV-úplný. 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é? - Kolika úsečkám dovolíme dotyk v jednom bodě? —> k-dotykové grafy - 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. .. Petr Hlinény, Fl MU Brno Fl: MA010: Průnikové grafy