Blackberry (grafteori)

I grafteorin är en björnbär för en oriktad graf G en familj av sammankopplade subgrafer av en graf G som berör varandra: för alla par av subgrafer som inte har gemensamma hörn måste det finnas en kant vars ändhörn ligger i dessa två subgrafer. Ordningen på björnbäret är den minsta storleken på vertexuppsättningen G som har en icke-tom skärningspunkt med varje subgraf av björnbäret. Björnbär används för att beskriva trädbredden på en graf G [1] .

Träets bredd och omslag

En täckning av ordningen k i en graf G är en funktion β som tar varje mängd X med mindre än k hörn till en ansluten komponent G  −  X på ett sådant sätt att två valfria delmängder β ( X ) och β ( Y ) berör varandra . Det vill säga bilderna av β bildar ett björnbär med ordningen k i G . Omvänt kan vilken björnbär som helst användas för att skapa ett skydd — för varje uppsättning X som är mindre än ordningen på björnbäret finns det en enda ansluten komponent β ( X ) som innehåller alla subgrafer i björnbäret som inte är anslutna till X .

Som Seymour och Thomas har visat beskriver ordningen för ett björnbär (eller, motsvarande skydd) trädbredden  - en graf har en björnbär av ordningen k om och endast om trädbredden är minst k − 1 [1] .

Storlek på björnbär

Som Grohe och Marx noterade, har avgränsade graders expanderare en trädbredd som är proportionell mot antalet hörn, och för att inkludera alla subgrafer som inte delar hörn med varje delmängd av den storleken, måste björnbäret för sådana grafer innehålla exponentiellt många distinkta subgrafer. Närmare bestämt, för dessa grafer måste även de björnbär vars ordning är något större än kvadratroten av trädbredden ha exponentiell storlek. Emellertid visade Groh och Marx också att varje graf med trädbredd k har en odling av polynomstorlek och ordning [2] .

Beräkningskomplexitet

Eftersom tröja kan ha exponentiell storlek är det inte alltid möjligt att konstruera dem i polynomtid för grafer med obegränsad trädbredd. Men om trädbredden är begränsad, är polynom konstruktionstid möjlig - det är möjligt att hitta en björnbär av ordningen k , om en sådan finns, i tiden , där n  är antalet hörn i grafen. Ännu snabbare algoritmer är möjliga för grafer med ett litet antal minimala separatorer [3] .

Bodlender, Grigoriev och Coster [4] studerade heuristiska algoritmer för att hitta björnbär av hög ordning. Deras metoder gav inte alltid björnbär med en ordning nära trädbredden, men för plana grafer ger de en konstant approximationsfaktor . Kreutzer och Tazari [5] föreslår polynom- tidsprobabilistiska sökalgoritmer på grafer med trädbredd k -hårtorn av polynomstorlek och ordning , vilket motsvarar den logaritmiska ordningsfaktorn som härleds av Grohe och Marx ( Grohe, Marx 2009 ) för förekomsten av odlingar av polynom. storlek.

Länkar

  1. ↑ 1 2 Paul D. Seymour, Robin Thomas. Grafsökning och en min-max-sats för trädbredd // Journal of Combinatorial Theory . - 1993. - T. 58 , nr. 1 . — S. 22–33 . - doi : 10.1006/jctb.1993.1027 . . I den här artikeln kallas björnbär "skärmar" och deras beställningar kallas "tjocklek".
  2. ↑ Martin Grohe, Daniel Marx. Om trädets bredd, tornens storlek och expansion // Journal of Combinatorial Theory . - 2009. - T. 99 , nr. 1 . — S. 218–228 . - doi : 10.1016/j.jctb.2008.06.004 . .
  3. ↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings. - Berlin: Springer, 2009. - T. 5734. - S. 223-234. - doi : 10.1007/978-3-642-03816-7_20 . .
  4. ↑ Bodlaender. Trädbredd nedre gränser med tornhår. — Algoritmik . - 2008. - T. 51. - S. 81–98. - doi : 10.1007/s00453-007-9056-z . .
  5. ↑ Stephan Kreutzer, Siamak Tazari. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). - 2010. - S. 354-364. .