Karakterisering af forbudte grafer

Forbudt grafkarakterisering er en metode til at beskrive en familie af grafer eller hypergrafer ved at specificere understrukturer, der er forbudt at optræde i nogen graf i familien.

Forbudte grafer

I grafteori kan mange vigtige familier af grafer beskrives ved et begrænset antal individuelle grafer, der ikke tilhører familien, og alle grafer fra familien, der indeholder nogen af ​​disse forbudte grafer som en (genereret) undergraf eller mindre, er udelukket . Prototypen på fænomenet er Pontryagin-Kuratovsky-sætningen , som siger, at en graf er plan (en graf, der kan tegnes på et plan uden skæringspunkter), hvis og kun hvis grafen ikke indeholder nogen af ​​de to forbudte undergrafer, en komplet graf K 5 og en komplet todelt graf K 3.3 .

I forskellige familier varierer karakteren af, hvad der er forbudt . Generelt er en struktur G et medlem af familien, hvis og kun hvis den forbudte struktur ikke er indeholdt i G . Den forbudte underbygning kan være en af:

Det sæt af strukturer, der er forbudt at tilhøre en given familie af grafer, kan også kaldes familiens obstruktionssæt .

Karakterisering af forbudte grafer kan bruges i algoritmer til at teste, om en graf tilhører en given familie. I mange tilfælde er det muligt at kontrollere i polynomisk tid, om en given graf indeholder et medlem af obstruktionssættet, og derfor om grafen tilhører familien defineret af obstruktionssættet.

For at en familie skal have en karakterisering ved forbudte grafer med en bestemt type understrukturer, skal familien lukkes i understrukturer. Det vil sige, at enhver understruktur (af en given type) af en graf i en familie skal være en anden graf i familien. Tilsvarende, hvis grafen ikke er i familien, skal alle store grafer, der indeholder den som en understruktur, også udelukkes fra familien. Hvis dette er sandt, er der altid et obstruktionssæt (sættet af grafer er ikke i familien, men alle mindre understrukturer er i familien). Men med en vis forståelse af, hvad der menes med en underbygning, kan dette obstruktionssæt vise sig at være uendeligt. Robertson-Seymour-sætningen beviser, at i visse tilfælde af mindreårige af grafen , har en mindre-lukket familie altid et begrænset obstruktionssæt.

Liste over forbudte grafkarakteriseringer (for grafer og hypergrafer)

Dette er en ufuldstændig liste og vil muligvis aldrig opfylde visse standarder for fuldstændighed. Du kan supplere det fra velrenommerede kilder .
Familie Forbudte kolonner Afhængighed Forbindelse
Skoven løkker, par parallelle kanter og cyklusser af enhver længde underafsnit Definition
sløjfe (til multigrafer) eller trekant K 3 (til simple grafer) Tæl mindre Definition
Tæller uden klør stjerne K 1,3 genereret undergraf Definition
Sammenlignelighedsgrafer genereret undergraf
Grafer uden trekanter trekant K 3 genereret undergraf Definition
Plane grafer K5 og K3.3 _ _ homøomorf subgraf Pontryagin-Kuratovsky teorem
K5 og K3.3 _ _ Tæl mindre Wagners sætning
Yderplanære grafer K4 og K2.3 _ _ Tæl mindre Distel, 4. Plane grafer, s. 115, ex. 23 [1]
Eksterne 1-plane grafer fem forbudte mindreårige Tæl mindre Auer, Bachmeier et al. [2]
Faste kønsgrafer finite obstruktionssæt (allerede til toroidale grafer med en størrelse på mindst 250815) Tæl mindre Distel, 12. Mindreårige, træer og fuldstændig forudbestilling, s. 387, ex. 53 [1]
Toptal begrænset obstruktionssæt Tæl mindre [3]

Grafer, der tillader indlejring uden links

Petersen familie af grafer Tæl mindre [fire]
Todelte grafer ulige cyklusser underafsnit [5]
Akkorde grafer cyklusser af længde 4 eller mere genereret undergraf [6]
Perfekte grafer ulige cyklusser af længde 5 eller mere og deres komplementer genereret undergraf [7]
Linjegrafer til grafer ni forbudte subgrafer (opført her ) genereret undergraf [otte]
Sammenslutninger af kaktusgrafer diamant dannet ved at fjerne en kant fra en komplet graf K 4 Tæl mindre [9]
trappe K 2,3 og dens dobbelte graf homøomorf subgraf [ti]
Cirkulære Helly bue grafer genereret undergraf [elleve]
Opdelt grafer genereret undergraf [12]
Parallel-sekventielle grafer ( træbredde , grenbredde ) K4 _ Tæl mindre Distel, 7. Extremal Graph Theory, s. 203, ex. 31 [1]
træets bredde K 5 , oktaeder , femkantet prisme , Wagner graf Tæl mindre [13]
træets bredde K4 _ Tæl mindre Distel, 12. Mindreårige, træer og fuldstændig forudbestilling, s. 370, eks. 12.6.2 [1]
Grenbredde K 5 , oktaeder , terning , Wagner graf Tæl mindre [fjorten]
Yderligere reducerbare grafer (kografer) Tæl P 4 genereret undergraf [femten]
Trivielt perfekte grafer Graf P 4 og cyklus C 4 genereret undergraf [16]
Tærskelgrafer Graf P 4 , cyklus C 4 og komplement C 4 genereret undergraf [16]
Linjegrafer af 3-homogene liniehypergrafer en begrænset liste over forbudte genererede undergrafer med minimumsgrad på mindst 19 genereret undergraf [17]
Linjegrafer k -homogene linjehypergrafer, k  > 3 en endelig liste over forbudte genererede undergrafer med minimum kantgrad på mindst 2 k 2  − 3 k  + 1 genereret undergraf [18] [19]
Grundlæggende teoremer
familie defineret ved afledt arvegods (ikke nødvendigvis endeligt) obstruktionssæt genereret undergraf
familie defineret af en mindre arvelig ejendom begrænset obstruktionssæt Tæl mindre Robertson-Seymour teorem

Se også

Noter

  1. ↑ 1 2 3 4 Reinhard Diestel. grafteori. Arkiveret 9. april 2011 på Wayback Machine GTM 173, 5. udgave 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, bind 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, Frankrig, 23.-25. september 2013, Revised Selected Papers / Stephen Wismat, Alexander Wolff,. - 2013. - T. 8242. - S. 107-118. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-319-03841-4_10 . .
  3. ↑ A. Gupta, R. Impagliazzo. Proc. 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. Linkløse indlejringer af grafer i 3-rum // Bulletin of the American Mathematical Society. - 1993. - T. 28 , no. 1 . — s. 84–89 . - doi : 10.1090/S0273-0979-1993-00335-5 . - arXiv : math/9301216 . .
  5. ↑ Béla Bollobas Moderne grafteori. - Springer, 1998. - ISBN 0-387-98488-7 .
  6. ↑ Toshinobu Kashiwabara. Graph Theory and Algorithms, 17. symposium for 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. — (Forelæsningsnotater i datalogi). - 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 , no. 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. Kompleksiteten af ​​nogle problemer med kantsletning // IEEE-transaktioner på kredsløb og systemer. - 1988. - T. 35 , no. 3 . — S. 354–362 . - doi : 10.1109/31.1748 . .
  10. ↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Kombinatoriske problemer på serieparallelle grafer // Diskret anvendt matematik. - 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ær-tidsgenkendelse af Helly Circular-Arc modeller og grafer // Algorithmica. - 2009. - T. 59 , no. 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. Et delvist k -arboret af grafer med afgrænset træbredde // Teoretisk datalogi. - 1998. - T. 209 , udg. 1-2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  14. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafer med grenbredde højst tre // Journal of Algorithms. - 1999. - T. 32 , no. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .
  15. ↑ D. Seinsche. På en egenskab af klassen af ​​n -farvelige 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 . Trivielt perfekte grafer // Diskret matematik. - 1978. - T. 24 , no. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
  17. ↑ Yury Metelsky, Regina Tyshkevich. On line grafer af lineære 3-uniforme hypergrafer // Journal of Graph Theory. - 1997. - Bd. 25. - Udgave. 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. Genkendelse af skæringsgrafer af lineære ensartede hypergrafer  // Grafer og 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æringsgrafer af k -ensartede hypergrafer // European J. Combinatorics. - 1982. - T. 3 . — S. 159–172 . - doi : 10.1016/s0195-6698(82)80029-2 .