Bramble (grafteori) - Bramble (graph theory)

En bramble av ordning fyra i ett 3 × 3 rutnätdiagram, bestående av sex ömsesidigt berörande anslutna underbilder

I grafteorin är en bramble för en oriktad graf G en familj av anslutna underbilder av G som alla berör varandra: för varje par ojämna underbilder måste det finnas en kant i G som har en slutpunkt i varje subgraf. Den ordning av en bramble är den minsta storleken på en träffuppsättning , en uppsättning av spetsar hos G som har en icke-tom skärningspunkt med vart och ett av subgrafer. Brambles kan användas för att karakterisera treewidth av G .

Trebredd och tillflyktsort

En oas av ordning k i en graf G är en funktion β som mappar varje uppsättning X på färre än k- hörn till en ansluten komponent av G  -  X , på ett sådant sätt att varannan delmängd β ( X ) och β ( Y ) berör varandra. Sålunda bildar bilduppsättningen av β en bram i G , med ordningen k . Omvänt kan varje bramble användas för att bestämma en fristad: för varje uppsättning X av storlek som är mindre än ordningen på bramble finns det en unik ansluten komponent β ( X ) som innehåller alla underbilderna i bramble som skiljer sig från X .

Som Seymour och Thomas visade, karaktäriserar ordningen på en bramble (eller motsvarande en fristad) trebredd : en graf har en bramble av ordning k om och bara om den har trebredd åtminstone k - 1 .

Storlek på brambles

Expanderdiagram med avgränsad grad har trebredden som är proportionell mot deras antal hörn, och har därför också ringar av linjär ordning. Men som Martin Grohe och Dániel Marx visade, för dessa grafer måste en bramble av så hög ordning innehålla exponentiellt många uppsättningar. Mer starkt, för dessa grafer måste även brambles vars ordning är något större än kvadratroten av träbredden ha exponentiell storlek. Grohe och Marx visade emellertid också att varje graf med trebredd k har en bramble av polynomstorlek och ordning . ${\ displaystyle \ Omega (k ^ {1/2} / \ log ^ {2} k)}$

Beräkningskomplexitet

Eftersom brambles kan ha exponentiell storlek är det inte alltid möjligt att konstruera dem i polynomtid för grafer med obegränsad trebredd. Men när träbredden är begränsad är en polynomisk tidskonstruktion möjlig: det är möjligt att hitta en bram av ordning k , när en existerar, i tid O ( n ^{k  + 2} ) där n är antalet hörn i den angivna grafen . Ännu snabbare algoritmer är möjliga för grafer med få minimala separatorer.

Bodlaender, Grigoriev och Koster studerade heuristik för att hitta brambles av hög ordning. Deras metoder genererar inte alltid ordningens ordning nära ingångsdiagrammets trebredd, men för plana grafer ger de ett konstant ungefärligt förhållande . Kreutzer och Tazari tillhandahåller randomiserade algoritmer som på grafer över trebredd k hittar brambles av polynomstorlek och ordning inom polynomial tid, inom en logaritmisk faktor av ordningen som visas av Grohe & Marx (2009) för att existera för polynomstorlek. ${\ displaystyle \ Omega (k ^ {1/2} / \ log ^ {3} k)}$

Riktade brambles

Begreppet bramble har också definierats för riktade grafer. I en riktad graf D är en bramble en samling starkt anslutna underbilder av D som alla rör varandra: för varje par av ojämna element X , Y i bramble måste det finnas en båge i D från X till Y och en från Y till X . Den ordning av en bramble är den minsta storleken på en träffuppsättning , en uppsättning hörn av D som har en icke-tom skärningspunkt med vart och ett av elementen i björnbär. Det björnbär antal av D är den maximala ordning en bramble i D . Bramble-numret för en riktad graf ligger inom en konstant faktor för dess riktade trebredd.

Referenser