Caracterizarea prin grafice interzise

Caracterizarea grafului interzis este o metodă de descriere a unei familii de grafuri sau hipergrafe prin specificarea substructurilor cărora le este interzis să apară în interiorul oricărui graf din familie.

Grafice interzise

În teoria graficelor, multe familii importante de grafice pot fi descrise printr-un număr finit de grafice individuale care nu aparțin familiei, iar toate graficele din familie care conțin oricare dintre aceste grafice interzise ca subgraf (generat) sau minor sunt excluse. . Prototipul fenomenului este teorema Pontryagin-Kuratovsky , care afirmă că un grafic este plan (un grafic care poate fi desenat pe un plan fără intersecții) dacă și numai dacă graficul nu conține niciunul dintre cele două subgrafe interzise, ​​un grafic complet . graficul K 5 și un grafic bipartit complet K 3.3 .

În diferite familii, natura a ceea ce este interzis variază. În general, o structură G este membru al familiei dacă și numai dacă structura interzisă nu este conținută în G . Substructura interzisă poate fi una dintre:

Mulțimea structurilor cărora le este interzis să aparțină unei anumite familii de grafuri poate fi numită și mulțimea de obstrucții a familiei.

Caracterizarea prin grafice interzise poate fi folosită în algoritmi pentru a testa dacă un grafic aparține unei anumite familii. În multe cazuri, este posibil să se verifice în timp polinomial dacă un grafic dat conține vreun membru al setului de obstacole și, prin urmare, dacă graficul aparține familiei definite de setul de obstrucții.

Pentru ca o familie să aibă o caracterizare prin grafice interzise cu un anumit tip de substructuri, familia trebuie să fie închisă în substructuri. Adică, orice substructură (de un anumit tip) a unui graf dintr-o familie trebuie să fie un alt graf din familie. În mod echivalent, dacă graficul nu este în familie, toate graficele mari care îl conțin ca substructură trebuie, de asemenea, excluse din familie. Dacă acest lucru este adevărat, există întotdeauna un set de obstrucții (setul de grafice nu este în familie, dar toate substructurile mai mici sunt în familie). Cu toate acestea, cu o anumită înțelegere a ceea ce se înțelege prin substructură, acest set de obstacole se poate dovedi infinit. Teorema Robertson–Seymour demonstrează că, în anumite cazuri de minori ai grafului , o familie minoră închisă are întotdeauna un set de obstrucții finit.

Lista caracterizărilor de grafice interzise (pentru grafice și hipergrafe)

Aceasta este o listă incompletă și este posibil să nu îndeplinească niciodată anumite standarde de exhaustivitate. Îl puteți completa din surse de renume .
Familie Coloane interzise Dependenta Conexiune
Pădure bucle, perechi de margini paralele și cicluri de orice lungime subgraf Definiție
buclă (pentru multigrafe) sau triunghi K 3 (pentru grafice simple) Conte minor Definiție
Numara fara gheare steaua K 1.3 subgraf generat Definiție
Grafice de comparabilitate subgraf generat
Grafice fără triunghiuri triunghiul K 3 subgraf generat Definiție
Grafice plane K5 și K3.3 _ _ subgraf homeomorf Teorema Pontriagin-Kuratovsky
K5 și K3.3 _ _ Conte minor teorema lui Wagner
Grafice exterioare K4 și K2.3 _ _ Conte minor Distel, 4. Grafice planare, p. 115, ex. 23 [1]
Grafice externe 1-planare cinci minori interzis Conte minor Auer, Bachmeier și colab. [2]
Grafice de gen fixe set finit de obstrucții (deja pentru graficele toroidale cu dimensiunea de cel puțin 250815) Conte minor Distel, 12. Minori, copaci și precomanda completă, p. 387, ex. 53 [1]
Numărarea apexelor set finit de obstacole Conte minor [3]

Grafice care admit încorporarea fără linkuri

Familia Petersen de grafice Conte minor [patru]
Grafice bipartite cicluri impare subgraf [5]
Grafice de acorduri cicluri de lungime 4 sau mai mare subgraf generat [6]
Grafice perfecte cicluri impare de lungime 5 sau mai mare și complementele acestora subgraf generat [7]
Grafice liniare pentru grafice nouă subgrafe interzise (enumerate aici ) subgraf generat [opt]
Uniri de grafice de cactus diamant format prin îndepărtarea unei muchii dintr-un grafic complet K 4 Conte minor [9]
scari K 2,3 și graficul său dual subgraf homeomorf [zece]
Grafice cu arc circular Helly subgraf generat [unsprezece]
Divizarea graficelor subgraf generat [12]
Grafice paralel-secvențiale ( treewidth , branchwidth ) K4 _ Conte minor Distel, 7. Teoria grafurilor extreme, p. 203, ex. 31 [1]
latimea lemnului K 5 , octaedru , prismă pentagonală , graf Wagner Conte minor [13]
latimea lemnului K4 _ Conte minor Distel, 12. Minori, copaci și precomanda completă, p. 370, Ex. 12.6.2 [1]
Lățimea ramurilor K 5 , octaedru , cub , graficul Wagner Conte minor [paisprezece]
Grafice reductibile suplimentare (cografe) Numărul P 4 subgraf generat [cincisprezece]
Grafice trivial de perfecte Graficul P 4 și Ciclul C 4 subgraf generat [16]
Grafice de prag Graficul P4 , ciclul C4 și complementul C4 _ subgraf generat [16]
Grafice liniare ale hipergrafelor cu 3 linii omogene o listă finită de subgrafe interzise generate cu un grad minim de cel puțin 19 subgraf generat [17]
Grafice cu linii k -hipergrafe cu linii omogene, k  > 3 o listă finită de subgrafe interzise generate cu un grad minim de margine de cel puțin 2 k 2  − 3 k  + 1 subgraf generat [18] [19]
Teoreme de bază
familie definită prin proprietate moștenită derivată (nu neapărat finit) set de obstrucții subgraf generat
familie definită de o proprietate ereditară minoră set finit de obstacole Conte minor Teorema Robertson–Seymour

Vezi și

Note

  1. ↑ 1 2 3 4 Reinhard Diesel. teoria grafurilor. Arhivat pe 9 aprilie 2011 pe Wayback Machine GTM 173, ediția a 5-a 2016/17. Springer-Verlag, Heidelberg. Texte de absolvent în matematică, volumul 173. ISBN 978-3-662-53621-6
  2. ↑ Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, Franta, 23-25 ​​septembrie 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. - 2013. - T. 8242. - S. 107-118. — (Note de curs în Informatică). - doi : 10.1007/978-3-319-03841-4_10 . .
  3. ↑ A. Gupta, R. Impagliazzo. Proc. Al 32-lea simpozion IEEE privind fundamentele informaticii (FOCS '91) . - IEEE Computer Society, 1991. - S. 802-811. - doi : 10.1109/SFCS.1991.185452 . .
  4. ↑ Neil Robertson, P.D. Seymour, Robin Thomas. Înglobare fără legătură de grafice în 3 spații // Buletinul Societății Americane de Matematică. - 1993. - T. 28 , nr. 1 . — p. 84–89 . - doi : 10.1090/S0273-0979-1993-00335-5 . - arXiv : math/9301216 . .
  5. ↑ Béla Bollobas Teoria modernă a grafurilor. - Springer, 1998. - ISBN 0-387-98488-7 .
  6. ↑ Toshinobu Kashiwabara. Teoria grafurilor și algoritmi, al 17-lea simpozion al Institutului de Cercetare a Comunicațiilor Electrice, Universitatea Tohoku, Sendai, Japonia, 24-25 octombrie 1980, Proceedings / Nobuji Saito, Takao Nishizeki. - Springer-Verlag, 1981. - T. 108. - S. 171-181. — (Note de curs în Informatică). - doi : 10.1007/3-540-10704-5\_15 . .
  7. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Teorema grafului perfect puternic // Analele matematicii . - 2006. - T. 164 , nr. 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. - Leipzig: Teubner, 1968. - S. 17-33. .
  9. ↑ Ehab El-Mallah, Charles Colbourn. Complexitatea unor probleme de ștergere a marginilor // Tranzacții IEEE pe circuite și sisteme. - 1988. - T. 35 , nr. 3 . — S. 354–362 . - doi : 10.1109/31.1748 . .
  10. ↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Probleme combinatorii pe grafuri serie-paralele // Matematică aplicată discretă. - 1981. - T. 3 , nr. 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. Recunoașterea liniară în timp a modelelor și graficelor Helly cu arc circular // Algorithmica. - 2009. - T. 59 , nr. 2 . — S. 215–239 . - doi : 10.1007/s00453-009-9304-5 .
  12. ↑ Stephane Földes, Peter L. Peter Hammer. Proceedings of the Eighth South-Eastern Conference on Combinatorics, Graph Theory and Computing (Univ. de stat Louisiana, Baton Rouge, La., 1977). - Winnipeg: Utilitas Math., 1977a. - T. XIX. — S. 311–315. — (Congressus Numerantium).
  13. ↑ Hans L. Bodlaender. Un k -arboretum parțial de grafice cu lățime de arbore mărginită // Informatică teoretică. - 1998. - T. 209 , nr. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  14. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafice cu lățimea ramurilor de cel mult trei // Journal of Algorithms. - 1999. - T. 32 , nr. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .
  15. ↑ D. Seinsche. Pe o proprietate a clasei de grafice n -colorabile // Journal of Combinatorial Theory, Seria B. - 1974. - Vol. 16 , nr. 2 . — S. 191–193 . - doi : 10.1016/0095-8956(74)90063-X .
  16. ↑ 12 Martin Charles Golumbic . Grafice trivial de perfecte // Matematică discretă. - 1978. - T. 24 , nr. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
  17. ↑ Iuri Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. - 1997. - Vol. 25. - Problema. 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. Recunoașterea graficelor de intersecție ale hipergrafelor liniare uniforme  // Grafice și combinatorie . - 1997. - T. 13 . — S. 359–367 . - doi : 10.1007/BF03353014 .
  19. ↑ Ranjan N. Naik, S.B. Rao, S.S. Shrikhande, N.M. Singhi. Grafice de intersecție ale k -hipergrafelor uniforme // European J. Combinatoric. - 1982. - T. 3 . — S. 159–172 . - doi : 10.1016/s0195-6698(82)80029-2 .