Karakterisering av förbjudna grafer

Förbjuden grafkarakterisering är en metod för att beskriva en familj av grafer eller hypergrafer genom att specificera understrukturer som är förbjudna att förekomma i någon graf i familjen.

Förbjudna grafer

I grafteorin kan många viktiga familjer av grafer beskrivas med ett ändligt antal individuella grafer som inte tillhör familjen, och alla grafer från familjen som innehåller någon av dessa förbjudna grafer som en (genererad) subgraf eller mindre är exkluderade . Prototypen av fenomenet är Pontryagin-Kuratovsky-satsen , som säger att en graf är plan (en graf som kan ritas på ett plan utan skärningspunkter) om och endast om grafen inte innehåller någon av de två förbjudna subgraferna, en komplett graf K 5 och en komplett tvådelad graf K 3.3 .

I olika familjer varierar karaktären på vad som är förbjudet . I allmänhet är en struktur G en medlem av familjen om och endast om den förbjudna strukturen inte finns i G . Den förbjudna understrukturen kan vara en av:

Den uppsättning strukturer som är förbjudna att tillhöra en given familj av grafer kan också kallas familjens obstruktionsuppsättning .

Karakterisering av förbjudna grafer kan användas i algoritmer för att testa om en graf tillhör en given familj. I många fall är det möjligt att kontrollera i polynomtid om en given graf innehåller någon medlem av obstruktionsuppsättningen, och därför om grafen tillhör familjen som definieras av obstruktionsuppsättningen.

För att en familj ska ha en karaktärisering av förbjudna grafer med en viss typ av understrukturer måste familjen slutas i understrukturer. Det vill säga att varje understruktur (av en given typ) av en graf i en familj måste vara en annan graf i familjen. På motsvarande sätt, om grafen inte är i familjen, måste alla stora grafer som innehåller den som en understruktur också uteslutas från familjen. Om detta är sant, finns det alltid en obstruktionsuppsättning (uppsättningen grafer som inte ingår i familjen, men alla mindre understrukturer finns i familjen). Men med en viss förståelse för vad som menas med en understruktur, kan denna obstruktionsuppsättning visa sig vara oändlig. Robertson-Seymour-satsen bevisar att i vissa fall av mindreåriga i grafen har en minor-sluten familj alltid en finit obstruktionsuppsättning.

Lista över förbjudna grafkarakteriseringar (för grafer och hypergrafer)

Detta är en ofullständig lista och kanske aldrig uppfyller vissa standarder för fullständighet. Du kan komplettera det från välrenommerade källor .
Familj Förbjudna kolumner Missbruk Förbindelse
Skogen slingor, par av parallella kanter och cykler av valfri längd subgraf Definition
loop (för multigrafer) eller triangel K 3 (för enkla grafer) Räkna mindre Definition
Räknar utan klor stjärna K 1.3 genererad subgraf Definition
Jämförbarhetsgrafer genererad subgraf
Grafer utan trianglar triangel K 3 genererad subgraf Definition
Plana grafer K5 och K3.3 _ _ homeomorf subgraf Pontryagin-Kuratovskys teorem
K5 och K3.3 _ _ Räkna mindre Wagners teorem
Outerplanar grafer K4 och K2.3 _ _ Räkna mindre Distel, 4. Plana grafer, sid. 115, ex. 23 [1]
Externa 1-planära grafer fem förbjudna minderåriga Räkna mindre Auer, Bachmeier et al. [2]
Fasta könsdiagram ändlig obstruktionsuppsättning (redan för toroidformade grafer med storleken minst 250815) Räkna mindre Distel, 12. Minderåriga, träd och fullständig förbeställning, sid. 387, ex. 53 [1]
Toppräkning ändlig obstruktionsuppsättning Räkna mindre [3]

Grafer som tillåter inbäddning utan länkar

Petersen familj av grafer Räkna mindre [fyra]
Tvådelade grafer udda cykler subgraf [5]
Ackordsgrafer cykler med längd 4 eller mer genererad subgraf [6]
Perfekta grafer udda cykler med längd 5 eller mer och deras komplement genererad subgraf [7]
Linjediagram för grafer nio förbjudna subgrafer (listade här ) genererad subgraf [åtta]
Fackföreningar av kaktusgrafer diamant bildad genom att ta bort en kant från en komplett graf K 4 Räkna mindre [9]
trappa K 2,3 och dess dubbla graf homeomorf subgraf [tio]
Cirkulära Helly bågegrafer genererad subgraf [elva]
Dela grafer genererad subgraf [12]
Parallellsekventiella grafer ( trädbredd , grenbredd ) K4 _ Räkna mindre Distel, 7. Extremal Graph Theory, sid. 203, ex. 31 [1]
vedens bredd K 5 , oktaeder , femkantigt prisma , Wagnergraf Räkna mindre [13]
vedens bredd K4 _ Räkna mindre Distel, 12. Minderåriga, träd och fullständig förbeställning, sid. 370, ex 12.6.2 [1]
Grenbredd K 5 , oktaeder , kub , Wagnergraf Räkna mindre [fjorton]
Ytterligare reducerbara grafer (kografer) Räkna P 4 genererad subgraf [femton]
Trivialt perfekta grafer Diagram P 4 och cykel C 4 genererad subgraf [16]
Tröskeldiagram Diagram P 4 , cykel C 4 och komplement C 4 genererad subgraf [16]
Linjediagram av 3-homogena linjehypergrafer en ändlig lista över förbjudna genererade subgrafer med minsta grad på minst 19 genererad subgraf [17]
Linjediagram k -homogena linjehypergrafer, k  > 3 en ändlig lista över förbjudna genererade subgrafer med minsta kantgrad på minst 2 k 2  − 3 k  + 1 genererad subgraf [18] [19]
Grundläggande satser
familj definierad av härledd ärvd egendom (inte nödvändigtvis ändlig) obstruktionsuppsättning genererad subgraf
familj definierad av en mindre ärftlig egendom ändlig obstruktionsuppsättning Räkna mindre Robertson-Seymours teorem

Se även

Anteckningar

  1. ↑ 1 2 3 4 Reinhard Diestel. grafteori. Arkiverad 9 april 2011 på Wayback Machine GTM 173, 5:e upplagan 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, volym 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, Frankrike, 23-25 ​​september 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. - 2013. - T. 8242. - S. 107-118. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-319-03841-4_10 . .
  3. ↑ A. Gupta, R. Impagliazzo. Proc. 32:a 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. Länklösa inbäddningar av grafer i 3-mellanrum // Bulletin of the American Mathematical Society. - 1993. - T. 28 , nr. 1 . — s. 84–89 . - doi : 10.1090/S0273-0979-1993-00335-5 . - arXiv : math/9301216 . .
  5. ↑ Béla Bollobas Modern grafteori. - Springer, 1998. - ISBN 0-387-98488-7 .
  6. ↑ Toshinobu Kashiwabara. Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, 24-25 oktober 1980, Proceedings / Nobuji Saito, Takao Nishizeki. - Springer-Verlag, 1981. - T. 108. - S. 171-181. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/3-540-10704-5\_15 . .
  7. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics . - 2006. - T. 164 , nr. 1 . — S. 51–229 . doi : 10.4007 / annals.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. Komplexiteten i vissa kantraderingsproblem // IEEE-transaktioner på kretsar och system. - 1988. - T. 35 , nr. 3 . — S. 354–362 . - doi : 10.1109/31.1748 . .
  10. ↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Kombinatoriska problem på serieparallella grafer // Diskret tillämpad matematik. - 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. Linjär-tidsigenkänning av Helly Circular-Arc-modeller och grafer // Algoritmik. - 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 Eightth 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. Ett partiellt k -arboretum av grafer med avgränsad trädbredd // Teoretisk datavetenskap. - 1998. - T. 209 , nummer. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  14. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafer med högst tre grenbredd // Journal of Algorithms. - 1999. - T. 32 , nr. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .
  15. ↑ D. Seinsche. På en egenskap av klassen n -färgbara grafer // Journal of Combinatorial Theory, Series B. - 1974. - Vol. 16 , nr. 2 . — S. 191–193 . - doi : 10.1016/0095-8956(74)90063-X .
  16. ↑ 12 Martin Charles Golumbic . Trivialt perfekta grafer // Diskret matematik. - 1978. - T. 24 , nr. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
  17. ↑ Yury Metelsky, Regina Tyshkevich. On line grafer av linjära 3-uniforma hypergrafer // Journal of Graph Theory. - 1997. - Vol. 25. - Fråga. 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. Att känna igen skärningsdiagram för linjära enhetliga hypergrafer  // Grafer och kombinatorik . - 1997. - T. 13 . — S. 359–367 . - doi : 10.1007/BF03353014 .
  19. ↑ Ranjan N. Naik, S.B. Rao, S.S. Shrikhande, N.M. Singhi. Skärningsdiagram av k -uniforma hypergrafer // European J. Combinatorics. - 1982. - T. 3 . — S. 159–172 . - doi : 10.1016/s0195-6698(82)80029-2 .