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
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127)
![S_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de6e810a93f67802ecb603ee0e3324005c6e583e)
![v_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127)
![v_{j}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5)
![E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/696aa9fbd2039bd92cc900d556cbc286b8021f14)
.
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127)
![S_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de6e810a93f67802ecb603ee0e3324005c6e583e)
![v_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127)
![S_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de6e810a93f67802ecb603ee0e3324005c6e583e)
![n^{2}/4](https://wikimedia.org/api/rest_v1/media/math/render/svg/46c0b98fd6439a0397e95ce0b4dd5545a5cdff5b)
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í:
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](https://wikimedia.org/api/rest_v1/media/math/render/svg/c07a0bc023490be1c08e6c33a9cdc93bec908224)
![f (x) \ podmnožina f (y)](https://wikimedia.org/api/rest_v1/media/math/render/svg/83a49621bd7db0c864b37e50b049be4134ee9575)
- Nervový povlak
Poznámky
- ↑ McKee, McMorris, 1999 .
- ↑ Erdős, Goodman, Posa, 1966 .
- ↑ Szpilrain-Marczewski, 1945 .
- ↑ Čulik, 1964 .
- ↑ Schaefer, 2010 .
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