Nedbrytning av grendiagram

I grafteorin är en grennedbrytning av en oriktad graf G  en hierarkisk klustring av kanterna på en graf G representerad av ett orotat binärt träd T med kanter från G som löv. Att ta bort valfri kant från T delar upp kanterna på G i två subgrafer, och sönderdelningens bredd är det maximala antalet gemensamma hörn i varje subgraf som erhålls på detta sätt. Förgreningsbredden för G är  den minsta bredden av eventuell nedbrytning av G till grenar.

Förgreningsbredden är nära relaterad till trädets bredd  - för alla grafer ligger de inom en konstant faktor från varandra, och båda kvantiteterna kan beskrivas av förbjudna mindreåriga . Precis som med trädbredd kan många optimeringsproblem på grafer effektivt lösas på grafer med små förgreningsbredder. Men till skillnad från trädbredden kan grenbredden för en plan graf beräknas exakt i polynomtid . Grennedbrytning och grenbredd kan generaliseras från grafer till matroider .

Definitioner

Ett orotat binärt träd  är en ansluten oriktad cykelfri graf där varje icke-bladsnod har exakt tre grannar. Grennedbrytning kan representeras som ett icke rotat binärt träd T tillsammans med en bijektion mellan bladen på trädet T och kanterna på den givna grafen G  = ( V , E ). Om e  är någon kant på trädet T , då delar man bort e från T i två underträd T 1 och T 2 . Denna uppdelning av trädet T i underträd resulterar i uppdelningen av kanterna som är associerade med bladen på trädet T i två undergrafer av grafen G , G 1 och G 2 . En sådan uppdelning av en graf G i två subgrafer kallas en e-partition .

Bredden på en e-partition är antalet hörn i G som faller in mot båda kanterna i E 1 och kanterna i E 2 . Det vill säga, detta är uppsättningen av hörn som är gemensamma för subgraferna G 1 och G 2 . Grennedbrytningsbredden är den maximala bredden på en e-partition. Förgreningsbredden för grafen G  är den minsta bredden av grennedbrytningar av grafen G .

Samband med trädets bredd

Grendiagramsnedbrytning är nära relaterad till trädnedbrytning , och grenbredd är nära relaterad till trädbredd . De två värdena skiljer sig inte mer än en konstant faktor. I synnerhet, i den tidning där de föreslog grenbredden, visade Neil Robertson och Paul Seymour [1] att för en graf G med trädbredd k och grenbredd b > 1

Skivningsbredd

Skivbredd är ett begrepp som definieras på samma sätt som grenbredd, med den enda skillnaden att hörn och kanter byts om i definitionerna. En sönderdelning är ett binärt träd utan rötter där varje blad representerar en vertex i den ursprungliga grafen, och skivningsbredden är antalet (eller totalvikten i viktade grafer) av kanter som faller in i vertexen i båda underträden.

Grenbreddsalgoritmer fungerar vanligtvis genom att reducera till ett likvärdigt skivningsbreddproblem. I synnerhet är skärningsbredden på den mittersta grafen exakt dubbelt så stor som förgreningsbredden på den ursprungliga grafen [2] .

Algoritmer och komplexitet

Problemet med att avgöra om en graf G har en grenupplösning med högst bredd k är NP-komplett om G och k är indata till problemet [2] . Emellertid bildar grafer med en förgreningsbredd som inte är större än k en familj av grafer slutna i moll [3] , varav det följer att beräkningen av förgreningsbredden är ett fast-parametriskt lösbart problem : det finns en algoritm för att beräkna den optimala grennedbrytningen vars gångtid är grafer med en grenbredd som inte överstiger k för någon konstant k beror linjärt på grafens storlek [4]

För plana grafer kan grenbredden beräknas i linjär tid. Detta i motsats till trädbredden, för vilken beräkningskomplexitet på plana grafer är ett välkänt öppet problem [5] . Paul Seymour och Robin Thomas ursprungliga planar grenbreddsalgoritm löste problemet i O( n 2 ) tid på en graf med n hörn, medan deras grennedbrytningsalgoritm körde i O( n 4 ) tid [2] . Den senare förbättrades senare till O( n 3 ) [6] .

Liksom med trädbredd kan grenbredd användas som bas för dynamiska programmeringsalgoritmer för många NP-hårda optimeringsproblem, och i dessa algoritmer kommer lösningstiden att vara exponentiell med bredden på ingångsgrafen eller matroiden [7] [8] . Till exempel använde Cook och Seymour [9] en grenbreddsbaserad dynamisk programmeringsmetod på problemet med att slå samman dellösningar av det resande säljarproblemet till en global lösning genom att bilda en gles graf från föreningen av dellösningar, för vilken heuristisk spektral klustring användes för att hitta en bra sönderdelning till grenar, varefter de tillämpade dynamisk programmering på den resulterande sönderdelningen. Fomin och Tilikos [10] hävdar att grenbredd fungerar bättre än trädbredd när man utvecklar fast-parametriskt avgörbara algoritmer på plana grafer av många skäl - grenbredden kan begränsas hårdare av en parameterfunktion än trädbreddsbegränsningen, det kan vara beräknas i polynomtid och grenbreddsberäkningsalgoritmen har inte stora dolda konstanter.

Generaliseringar för matroider

Man kan också definiera begreppet grennedbrytning för matroider , som generaliserar grenupplösning av grafer [11] . En matroidgrennedbrytning är en hierarkisk klustring av matroidelement, representerade som ett icke-rotat binärt träd med matroidelement som löv. För matroider kan e-partition definieras på samma sätt som för grafer, och som ett resultat får vi en partition av mängden M av matroidelement i två delmängder A och B . Om vi ​​betecknar rangfunktionen för en matroid med ρ, så definieras bredden av en e-partition som ρ( A ) + ρ( B ) − ρ( M ) + 1 , och nedbrytningsbredden och matroidförgreningens bredd definieras liknande definitionerna för en graf. Grafens förgreningsbredd och förgreningsbredden för motsvarande grafmatroid kan skilja sig åt. Till exempel har en 3- kantsbana och en 3-kantsstjärna olika grenbredder, 2 respektive 1, men grafmatroiden för dem är densamma och den har en grenbredd på 1 [12] . För grafer utan träd är emellertid grafens förgreningsbredd lika med förgreningsbredden för den tillhörande grafmatroiden [12] [13] . Förgreningsbredden för en matroid är lika med förgreningsbredden för dess dubbla matroid , och det följer särskilt att förgreningsbredden för varje plan graf som inte är ett träd är lika med förgreningsbredden för dess dubbla graf [12 ] .

Grenbredd är en viktig komponent i försöken att utvidga grafminorteori till matroida mindreåriga  — även om trädbredden också kan generaliseras till matroider [14] och spelar en större roll i grafminorteori än grenbredd, så har grenbredden bekvämare egenskaper i matroider [15] . Robertson och Seymour gissade att matroider som kan representeras av ett visst ändligt fält är helt kvasi-ordnade , vilket är analogt med Robertson-Seymours sats för grafer, men gissningen har bara bevisats för matroider med begränsad grenbredd [16] [ 15] . Dessutom, om en familj av matroider stängda i moll och representerade av ett ändligt fält inte inkluderar grafiska matroider för alla plana grafer, så finns det en konstant begränsning av förgreningsbredden i familjen, vilket generaliserar motsvarande uttalande för graffamiljer stängd i minderåriga [15] [17] .

För vilken fast k som helst kan matroider med högst k förgreningsbredd kännas igen i polynomtid av en algoritm som kommer åt matroiden via ett oberoende orakel [18] .

Illegala minderåriga

Genom Robertson-Seymour-satsen kan grafer med grenbredd k karakteriseras av en ändlig uppsättning förbjudna minderåriga . Grafer med grenbredd 0 är matchningar , och de minsta förbjudna minorerna i detta fall är en bana med två bågar och en triangulär graf (och även en cykel av två bågar om multigrafer beaktas) [19] . Grafer med grenbredd 1 är grafer där varje ansluten komponent är en stjärna , och de minsta förbjudna mindre för grafer med grenbredd 1 är en triangulär graf (eller en cykel med två bågar om flergrafer beaktas) och trebågsbanor [19 ] . Grafer med grenbredd 2 är grafer där varje bikopplad komponent är en parallell-seriell graf , och den enda minimala förbjudna minor är en komplett graf K 4 av fyra hörn [19] . En graf har en grenbredd tre om och endast om dess trädbredd är tre och den inte har en hyperkubgraf som bi. Således är de fyra förbjudna minorerna tre av de fyra förbjudna minorerna av grafer med trädbredd tre ( oktaedergrafen , den kompletta K 5 -grafen och Wagnergrafen ) tillsammans med kubgrafen [20] .

Förbjudna minderåriga studeras också för matroidförgreningens bredd, trots avsaknaden av en fullständig analogi av Robertson-Seymour-satsen i detta fall. En matroid har grenbredd ett om och bara om något element är antingen en loop eller en coloop, så den enda minimala förbjudna moll är den homogena matroiden U(2,3), grafmatroiden för den triangulära grafen. En matroid har grenbredd två om och bara om det är en grafisk matroid av en graf med grenbredd två, så de minsta förbjudna minorerna är grafmatroiderna i grafen K 4 och den icke-grafiska matroiden U(2,4). Matroider med förgreningsbredd tre är inte helt kvasi-ordnade utan ytterligare antagande om en representation över ett ändligt fält, men ändå har matroider med någon avgränsad förgreningsbredd ett ändligt antal minimala förbjudna minderåriga, som har ett antal element som beror på på förgreningsbredden som mest exponentiellt [21 ] [22] .

Anteckningar

  1. ↑ Robertson, Seymour, 1991 , sid. 168, sats 5.1.
  2. ↑ 1 2 3 Seymour, Thomas, 1994 .
  3. ↑ Robertson, Seymour, 1991 , sid. 164, sats 4.1.
  4. ↑ Bodlaender, Thilikos (1997 ). Fomin, Mazoit och Todinka Fomin, Mazoit, Todinca (2009 ) beskriver en algoritm med förbättrat beroende av k , (2√3) k , men beroendet av antalet hörn ökar från linjär till kvadratisk.
  5. ↑ Kao, 2008 .
  6. ↑ Gu, Tamaki, 2008 .
  7. ↑ Hicks, 2000 .
  8. ↑ Hliněny, 2003 .
  9. ↑ Cook, Seymour, 2003 .
  10. ↑ Fomin, Thilikos, 2006 .
  11. ↑ Robertson, Seymour, 1991 , sid. 188–190, avsnitt 12, "Tangles and Matroids."
  12. ↑ 1 2 3 Mazoit, Thomasse, 2007 .
  13. ↑ Hicks, McMurray, 2007 .
  14. ↑ Hliněny, Whittle, 2006 .
  15. ↑ 1 2 3 Geelen, Gerards, Whittle, 2006 .
  16. ↑ Geelen, Gerards, Whittle, 2002 .
  17. ↑ Geelen, Gerards, Whittle, 2007 .
  18. ↑ Oum, Seymour, 2007 .
  19. ↑ 1 2 3 Robertson, Seymour, 1991 , sid. 165, sats 4.2.
  20. ↑ Bodlaender, Thilikos (1999 ). Den fjärde förbjudna moll för trädbredd tre, den femkantiga prismagrafen, har kubgrafen som sin moll, så den är inte minimal för grenbredd tre.
  21. ↑ Hall, Oxley, Semple, Whittle, 2002 .
  22. ↑ Geelen, Gerards, Robertson, Whittle, 2003 .

Litteratur