Charakterizace zakázanými grafy

Charakterizace zakázaných grafů je metoda popisu rodiny grafů nebo hypergrafů určením podstruktur, které se nesmí objevit v žádném grafu v rodině.

Zakázané grafy

V teorii grafů lze mnoho důležitých rodin grafů popsat konečným počtem jednotlivých grafů, které do rodiny nepatří, a všechny grafy z rodiny, které obsahují některý z těchto zakázaných grafů jako (generovaný) podgraf nebo vedlejší grafy, jsou vyloučeny. . Prototypem jevu je Pontrjaginova-Kuratovského věta , která říká, že graf je rovinný (graf, který lze nakreslit v rovině bez průsečíků) právě tehdy, když graf neobsahuje žádný ze dvou zakázaných podgrafů, úplný graf K 5 a úplný bipartitní graf K 3.3 .

V různých rodinách se povaha toho, co je zakázáno , liší. Obecně platí, že struktura G je členem rodiny právě tehdy, když zakázaná struktura není obsažena v G . Zakázaná podstruktura může být jedna z:

Množinu struktur, které je zakázáno patřit do dané rodiny grafů, můžeme také nazvat obstrukční množinou rodiny.

Charakterizaci zakázanými grafy lze v algoritmech použít k testování, zda graf patří do dané rodiny. V mnoha případech je možné v polynomiálním čase zkontrolovat, zda daný graf obsahuje nějakého člena množiny překážek, a tedy zda graf patří do rodiny definované množinou překážek.

Aby rodina měla charakterizaci zakázanými grafy s určitým typem substruktur, musí být rodina uzavřena v substrukturách. To znamená, že jakákoli podstruktura (daného typu) grafu v rodině musí být dalším grafem v rodině. Stejně tak, pokud graf není v rodině, všechny velké grafy, které jej obsahují jako podstrukturu, musí být z rodiny také vyloučeny. Pokud je to pravda, vždy existuje množina překážek (množina grafů není v rodině, ale všechny menší podstruktury jsou v rodině). S určitým pochopením toho, co je míněno podstrukturou, se však tato sada překážek může ukázat jako nekonečná. Robertsonův-Seymourův teorém dokazuje, že v určitých případech nezletilých v grafu má uzavřená rodina vždy konečnou množinu překážek.

Seznam zakázaných charakterizací grafů (pro grafy a hypergrafy)

Toto je neúplný seznam a nemusí nikdy splňovat určité standardy úplnosti. Můžete jej doplnit z renomovaných zdrojů .
Rodina Zakázané sloupy Závislost Spojení
Lesy smyčky, dvojice rovnoběžných hran a cykly libovolné délky podgraf Definice
smyčka (pro multigrafy) nebo trojúhelník K 3 (pro jednoduché grafy) Hrabě menší Definice
Počítá bez drápů hvězda K 1.3 vygenerovaný podgraf Definice
Grafy srovnatelnosti vygenerovaný podgraf
Grafy bez trojúhelníků trojúhelník K 3 vygenerovaný podgraf Definice
Rovinné grafy K5 a K3.3 _ _ homeomorfní podgraf Pontrjaginova-Kuratovského věta
K5 a K3.3 _ _ Hrabě menší Wagnerova věta
Mimorovinné grafy K4 a K2.3 _ _ Hrabě menší Distel, 4. Rovinné grafy, str. 115, býv. 23 [1]
Externí 1-rovinné grafy pět zakázaných nezletilých Hrabě menší Auer, Bachmeier a kol. [2]
Opravené grafy pohlaví konečná sada překážek (již pro toroidní grafy o velikosti alespoň 250815) Hrabě menší Distel, 12. Nezletilí, stromy a kompletní předobjednávka, str. 387, býv. 53 [1]
Počet vrcholů soubor konečných překážek Hrabě menší [3]

Grafy připouštějící vkládání bez odkazů

Petersenova rodina grafů Hrabě menší [čtyři]
Bipartitní grafy liché cykly podgraf [5]
Chordální grafy cykly o délce 4 nebo více vygenerovaný podgraf [6]
Perfektní grafy liché cykly o délce 5 a více a jejich doplňky vygenerovaný podgraf [7]
Spojnicové grafy pro grafy devět zakázaných podgrafů (uvedeno zde ) vygenerovaný podgraf [osm]
Spojení kaktusových grafů diamant vzniklý odstraněním hrany z úplného grafu K 4 Hrabě menší [9]
schody K 2,3 a jeho duální graf homeomorfní podgraf [deset]
Kruhové Hellyho obloukové grafy vygenerovaný podgraf [jedenáct]
Rozdělené grafy vygenerovaný podgraf [12]
Paralelně sekvenční grafy ( treewidth , branchwidth ) K4 _ Hrabě menší Distel, 7. Extremal Graph Theory, str. 203, ex. 31 [1]
šířka dřeva K 5 , osmistěn , pětiboký hranol , Wagnerův graf Hrabě menší [13]
šířka dřeva K4 _ Hrabě menší Distel, 12. Nezletilí, stromy a kompletní předobjednávka, str. 370, Př. 12.6.2 [1]
Šířka větve K 5 , osmistěn , krychle , Wagnerův graf Hrabě menší [čtrnáct]
Další redukovatelné grafy (cographs) Hrabě P 4 vygenerovaný podgraf [patnáct]
Triviálně dokonalé grafy Graf P 4 a cyklus C 4 vygenerovaný podgraf [16]
Prahové grafy Graf P 4 , cyklus C 4 a doplněk C 4 vygenerovaný podgraf [16]
Spojnicové grafy 3-homogenních spojnicových hypergrafů konečný seznam zakázaných generovaných podgrafů s minimálním stupněm alespoň 19 vygenerovaný podgraf [17]
Spojnicové grafy k -homogenní spojnicové hypergrafy, k  > 3 konečný seznam zakázaných generovaných podgrafů s minimálním stupněm hrany alespoň 2 k 2  − 3 k  + 1 vygenerovaný podgraf [18] [19]
Základní věty
rodina definovaná odvozeným zděděným majetkem (ne nutně konečná) množina překážek vygenerovaný podgraf
rodina vymezená drobným dědičným majetkem soubor konečných překážek Hrabě menší Robertsonova-Seymourova věta

Viz také

Poznámky

  1. ↑ 1 2 3 4 Reinhard Diestel. teorie grafů. Archivováno 9. dubna 2011 na Wayback Machine GTM 173, 5. vydání 2016/17. Springer-Verlag, Heidelberg. Postgraduální texty z matematiky, svazek 173. ISBN 978-3-662-53621-6
  2. ↑ Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21. mezinárodní symposium, GD 2013, Bordeaux, Francie, 23.-25. září 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. - 2013. - T. 8242. - S. 107-118. — (Poznámky z informatiky). - doi : 10.1007/978-3-319-03841-4_10 . .
  3. ↑ A. Gupta, R. Impagliazzo. Proč. 32. IEEE Symposium on Foundations of Computer Science (FOCS '91) . - IEEE Computer Society, 1991. - S. 802-811. - doi : 10.1109/SFCS.1991.185452 . .
  4. ↑ Neil Robertson, P.D. Seymour, Robin Thomas. Bezpropojkové vkládání grafů do 3prostoru // Bulletin Americké matematické společnosti. - 1993. - T. 28 , no. 1 . — s. 84–89 . - doi : 10.1090/S0273-0979-1993-00335-5 . - arXiv : math/9301216 . .
  5. ↑ Béla Bollobas Moderní teorie grafů. - Springer, 1998. - ISBN 0-387-98488-7 .
  6. ↑ Toshinobu Kashiwabara. Teorie grafů a algoritmy, 17. symposium Výzkumného ústavu elektrické komunikace, Univerzita Tohoku, Sendai, Japonsko, 24. až 25. října 1980, sborník příspěvků / Nobuji Saito, Takao Nishizeki. - Springer-Verlag, 1981. - T. 108. - S. 171-181. — (Poznámky z informatiky). - doi : 10.1007/3-540-10704-5\_15 . .
  7. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Věta o silném dokonalém grafu // Annals of Mathematics . - 2006. - T. 164 , č. 1 . — S. 51–229 . doi : 10.4007 / anals.2006.164.51 . - arXiv : math/0212070v1 . .
  8. ↑ LW Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, H.J. Walter. - Lipsko: Teubner, 1968. - S. 17-33. .
  9. ↑ Ehab El-Mallah, Charles Colbourn. Složitost některých problémů s odstraněním okrajů // IEEE Transactions on Circuits and Systems. - 1988. - T. 35 , no. 3 . — S. 354–362 . - doi : 10.1109/31.1748 . .
  10. ↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Kombinatorické úlohy na sérioparalelních grafech // Diskrétní aplikovaná matematika. - 1981. - T. 3 , no. 1 . — S. 75–76 . - doi : 10.1016/0166-218X(81)90031-7 . .
  11. ↑ Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Lineární rozpoznávání modelů a grafů Helly Circular-Arc // Algorithmica. - 2009. - T. 59 , č.p. 2 . — S. 215–239 ​​. - doi : 10.1007/s00453-009-9304-5 .
  12. ↑ Stephane Földes, Peter L. Peter Hammer. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). - Winnipeg: Utilitas Math., 1977a. - T. XIX. — S. 311–315. — (Congressus Numerantium).
  13. ↑ Hans L. Bodlaender. Částečné k -arboretum grafů s omezenou šířkou stromu // Teoretická informatika. - 1998. - T. 209 , vydání. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  14. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafy s šířkou větve nejvýše tři // Journal of Algorithms. - 1999. - T. 32 , no. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .
  15. ↑ D. Seinsche. O vlastnosti třídy n -zabarvitelných grafů // Journal of Combinatorial Theory, Series B. - 1974. - Vol.16 , no . 2 . — S. 191–193 . - doi : 10.1016/0095-8956(74)90063-X .
  16. ↑ 12 Martin Charles Golumbic . Triviálně dokonalé grafy // Diskrétní matematika. - 1978. - T. 24 , no. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
  17. ↑ Yury Metelsky, Regina Tyshkevich. On line grafy lineárních 3-uniformních hypergrafů // Journal of Graph Theory. - 1997. - Sv. 25. - Vydání. 4 . — S. 243–251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  18. ↑ MS Jacobson, Andre E. Kézdy, Jeno Lehel. Rozpoznávání průnikových grafů lineárních uniformních hypergrafů  // Grafy a kombinatorika . - 1997. - T. 13 . — S. 359–367 . - doi : 10.1007/BF03353014 .
  19. ↑ Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Průnikové grafy k -uniformních hypergrafů // European J. Combinatorics. - 1982. - T. 3 . — S. 159–172 . - doi : 10.1016/s0195-6698(82)80029-2 .