Průsečíkový graf

V teorii grafů je průsečíkový graf graf reprezentující schéma průsečíku rodiny množin . Jakýkoli graf může být reprezentován jako průsečíkový graf, ale některé důležité speciální třídy lze definovat z hlediska typů množin používaných pro reprezentaci jako množiny průniků.

Přehled teorie průnikových grafů a důležité speciální třídy průnikových grafů viz McKee a McMorris [1] .

Formální definice

Průsečíkový graf je neorientovaný graf vytvořený z rodiny množin

S_{i},i=0,1,2,...

vytvořením vrcholu pro každou množinu a spojením dvou vrcholů a hrany, pokud mají odpovídající dvě množiny neprázdný průsečík, tzn. $v_{i}$ $S_{i}$ $v_{i}$ $v_{j}$

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

Všechny grafy jsou průnikové grafy

Libovolný neorientovaný graf G lze znázornit jako průsečíkový - pro libovolný vrchol grafu G tvoříme množinu skládající se z hran spadajících do . Dvě takové množiny mají neprázdný průsečík právě tehdy, když odpovídající vrcholy patří stejné hraně. Erdős, Goodman a Poza [2] ukázali efektivnější konstrukci (která vyžaduje méně prvků ve všech množinách ), ve které celkový počet prvků v množinách nepřesahuje , kde n je počet vrcholů v grafu. Jejich tvrzení, že všechny grafy jsou průnikové grafy, zaznamenal Marchevskij [3] , ale také doporučili podívat se na Chulikovo dílo [4] . Počet průsečíků grafu je minimální počet prvků v reprezentaci grafu jako průsečíkového grafu. $v_{i}$ $S_{i}$ $v_{i}$ $S_{i}$ $n^{2}/4$

Třídy průnikových grafů

Mnoho důležitých rodin grafů lze popsat jako průsečíkové grafy omezených typů množin, jako jsou množiny odvozené z určitých geometrických konfigurací:

Intervalový graf je definován jako graf průsečíků intervalů na lince nebo spojených podgrafů cest .
Kruhový obloukový graf je definován jako průsečíkový graf kruhového oblouku .
Graf mnohoúhelníků na kružnici je definován jako graf průsečíků mnohoúhelníků s vrcholy ležícími na kružnici.
Jednou z charakteristik akordických grafů je to, že se jedná o průsečíkové grafy spojených podgrafů stromu .
Lichoběžníkový graf je definován jako graf průsečíků lichoběžníků tvořených dvěma rovnoběžnými čarami. Jsou zobecněním pojmu permutační graf , které jsou zase speciálním případem rodiny komplementu grafů srovnatelnosti , známé jako grafy kosrovnatelnosti.
Jednotkový kruhový graf je definován jako průsečík jednotkových kruhů v rovině.
Věta o balení kruhu říká, že rovinné grafy jsou přesně průsečíkové grafy rodin uzavřených disjunktních (dotykových povolených) disků v rovině.
Scheinermanův dohad (nyní teorém) říká, že jakýkoli rovinný graf lze znázornit jako graf průsečíků úseček v rovině. Grafy průsečíků úseček na přímce však mohou být nerovinné a rozpoznávání grafů průsečíků úseček na přímce je pro teorii existence reálných čísel kompletní 5] .
Spojnicový graf grafu G je definován jako průsečík hran grafu G , kde každá hrana je považována za množinu dvou jeho koncových vrcholů.
Řetězcový graf je graf průsečíků křivek v rovině .
Graf má rámec k , pokud se jedná o průsečíkový graf vícerozměrných obdélníků dimenze k , ale ne menších rozměrů.

Variace a zobecnění

Teoretickými obdobami řádu průnikových grafů jsou řády vnoření . Stejným způsobem, jakým reprezentace grafu průniku označí každý vrchol sadou hran, které k němu přiléhají a které mají neprázdný průsečík, označí reprezentace pořadí vnoření f částečně uspořádané sady každý prvek množinou tak, že pro libovolné x a y v něm tehdy a jen tehdy, když . $x\leq y$ $f (x) \ podmnožina f (y)$
Nervový povlak

Literatura

K. Čulík. Teorie grafů a její aplikace (Proc. Sympos. Smolenice, 1963). — Praha: Publ. Dům čs. akad. Sci., 1964, str. 13-20.
Paul Erdős, A. W. Goodman, Louis Posa. Reprezentace grafu pomocí množin průsečíků // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Algoritmická teorie grafů a dokonalé grafy. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Témata z teorie průsečíkových grafů. - Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku, 1999. - Svazek 2. - (SIAM Monographs on Discrete Mathematics and Applications). — ISBN 0-89871-430-3 .
E. Szpilrain-Marczewski. Sur deux propriétés des class d'ensembles // Fond. Matematika. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schaefer. Grafická kresba, 17. mezinárodní symposium, GS 2009, Chicago, IL, USA, září 2009, revidované příspěvky . - Springer-Verlag, 2010. - Sv. 5849. - S. 334-344. — (Poznámky z informatiky). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .

Odkazy

Jan Kratochvíl, Video přednáška o průsečíkových grafech (červen 2007) Archivováno 17. února 2020 na Wayback Machine
E. Prisner, A Journey through Intersection Graph County Archived 24. dubna 2021 na Wayback Machine