Grafbandbredd - Graph bandwidth

I grafteori , den graf bandbredd problemet är att märka n vertex v _jag av en graf G med distinkta heltal f ( v _i ) så att mängden minimeras ( E är kanten uppsättning av G ). Problemet kan visualiseras som att placera hörn i en graf vid distinkta heltalspunkter längs x -axeln så att längden på den längsta kanten minimeras. Sådan placering kallas linjär grafarrangemang , linjär graflayout eller linjär grafplacering . ${\ displaystyle \ max \ {\, | f (v_ {i}) - f (v_ {j}) |: v_ {i} v_ {j} \ i E \, \}}$

Den viktade graf bandbreddsproblem är en generalisering varvid kanterna är tilldelade vikter w _ij och kostnadsfunktionen skall minimeras är . ${\ displaystyle \ max \ {\, w_ {ij} | f (v_ {i}) - f (v_ {j}) |: v_ {i} v_ {j} \ i E \, \}}$

När det gäller matriser är den (ovägda) grafbandbredden bandbredden för den symmetriska matrisen, som är kurvan för kurvan. Bandbredden kan också definieras som en mindre än den maximala klickstorleken i ett korrekt intervallbild av den angivna grafen, vald för att minimera dess klickstorlek ( Kaplan & Shamir 1996 ).

Bandbreddsformler för vissa grafer

För flera familjer av grafer ges bandbredden med en uttrycklig formel. ${\ displaystyle \ varphi (G)}$

Bandbredden för en bana graf P _n på n hörn är ett, och för en fullständig graf K _m vi har . För den fullständiga bipartitgrafen K _{m , n} , ${\ displaystyle \ varphi (K_ {n}) = n-1}$

${\ displaystyle \ varphi (K_ {m, n}) = \ lgolv (m-1) / 2 \ rgolv + n}$ antar ${\ displaystyle m \ geq n \ geq 1,}$

vilket bevisades av Chvátal. Som ett speciellt fall av denna formel har stjärndiagrammet på k  + 1-hörn bandbredd . ${\ displaystyle S_ {k} = K_ {k, 1}}$${\ displaystyle \ varphi (S_ {k}) = \ lfloor (k-1) / 2 \ rfloor +1}$

För hyperkub grafen på vertex bandbredden bestämdes genom Harper (1966) för att vara ${\ displaystyle Q_ {n}}$${\ displaystyle 2 ^ {n}}$

${\ displaystyle \ varphi (Q_ {n}) = \ sum _ {m = 0} ^ {n-1} {\ binom {m} {\ lfloor m / 2 \ rfloor}}.}$

Chvatálová visade att bandbredden för m  ×  n kvadratiska rutnätdiagram , det vill säga den kartesiska produkten av två bandiagram på och hörn, är lika med min { m , n }. ${\ displaystyle P_ {m} \ times P_ {n}}$${\ displaystyle m}$${\ displaystyle n}$

Gräns

Bandbredden för en graf kan begränsas i termer av olika andra grafparametrar. Exempelvis låta χ ( G ) beteckna kromatiska antal av G ,

${\ displaystyle \ varphi (G) \ geq \ chi (G) -1;}$

att låta diam ( G ) beteckna diametern på G , gäller följande ojämlikheter:

${\ displaystyle \ lceil (n-1) / \ operatorname {diam} (G) \ rceil \ leq \ varphi (G) \ leq n- \ operatorname {diam} (G),}$

var är antalet hörn i . ${\ displaystyle n}$${\ displaystyle G}$

Om en graf G har bandbredd k är dess vägbredd högst k ( Kaplan & Shamir 1996 ), och dess trädjup är högst k  log ( n / k ) ( Gruber 2012 ). I kontrast, såsom noterats i föregående avsnitt, stjärnan grafen S _k , en strukturellt mycket enkelt exempel på en träd , har jämförelsevis stor bandbredd. Observera att pathwidth av S _k är 1, och dess träddjupet är 2.

Vissa graffamiljer med avgränsad grad har sublinjär bandbredd: Chung (1988) visade att om T är högst ett träd med maximal grad ∆,

${\ displaystyle \ varphi (T) \ leq {\ frac {5n} {\ log _ {\ Delta} n}}.}$

Mer allmänt gäller att för plana grafer med högst begränsad maximal grad ∆ , har en liknande gräns (se Böttcher et al. 2010 ):

${\ displaystyle \ varphi (G) \ leq {\ frac {20n} {\ log _ {\ Delta} n}}.}$

Beräknar bandbredden

Både de oviktade och viktade versionerna är speciella fall av det kvadratiska tilldelningsproblemet för flaskhalsen . Bandbreddsproblemet är NP-svårt , även i vissa speciella fall. När det gäller förekomsten av effektiva approximationsalgoritmer är det känt att bandbredden är NP-svår att approximera inom någon konstant, och detta gäller även när ingångsdiagrammen är begränsade till larvträd med maximal hårlängd 2 ( Dubey, Feige & Unger 2010 ) . För täta diagram ritades en 3-approximationsalgoritm av Karpinski, Wirtgen & Zelikovsky (1997) . Å andra sidan är ett antal polynomiskt lösbara specialfall kända. En heuristisk algoritm för att erhålla linjära graflayouter med låg bandbredd är algoritmen Cuthill – McKee . Snabb algoritm för flera nivåer för beräkning av grafbandbredd föreslogs i.

Applikationer

Intresset för detta problem kommer från vissa applikationsområden.

Ett område är sparsam matris / bandmatrishantering , och allmänna algoritmer från detta område, såsom Cuthill – McKee-algoritmen , kan användas för att hitta ungefärliga lösningar för grafbandbreddsproblemet.

En annan applikationsdomän är inom elektronisk designautomation . I standardmetoden för celldesign har vanliga standardceller samma höjd och placeringen är ordnad i ett antal rader. I detta sammanhang modellerar grafbandbreddsproblem problemet med placering av en uppsättning standardceller i en enda rad i syfte att minimera den maximala utbredningsfördröjningen (som antas vara proportionell mot trådlängden).

Se även

• Pathwidth , ett annat NP-komplett optimeringsproblem med linjära layouter av grafer.

Referenser

• Böttcher, J .; Pruessmann, KP; Taraz, A .; Würfl, A. (2010). "Bandbredd, expansion, trebredd, separatorer och universalitet för avgränsade grafer". European Journal of Combinatorics . 31 (5): 1217–1227. arXiv : 0910.3014 . doi : 10.1016 / j.ejc.2009.10.010 .
• Chinn, PZ ; Chvátalová, J .; Dewdney, AK ; Gibbs, NE (1982). "Problemet med bandbredd för grafer och matriser - en undersökning". Journal of Graph Theory . 6 (3): 223–254. doi : 10.1002 / jgt.3190060302 .
• Chung, Fan RK (1988), "Etiketter av grafer", i Beineke, Lowell W .; Wilson, Robin J. (red.), Selected Topics in Graph Theory (PDF) , Academic Press, s. 151–168, ISBN   978-0-12-086203-0
• Dubey, C .; Feige, U .; Unger, W. (2010). "Hårdhetsresultat för ungefärlig bandbredd". Journal of Computer and System Sciences . 77 : 62–90. doi : 10.1016 / j.jcss.2010.06.006 .
• Garey, MR ; Johnson, DS (1979). Datorer och intraherbarhet: En guide till teorin om NP-fullständighet . New York: WH Freeman. ISBN   0-7167-1045-5 .
• Gruber, Hermann (2012), "On Balanced Separators, Treewidth, and Cycle Rank", Journal of Combinatorics , 3 (4): 669–682, arXiv : 1012.1344 , doi : 10.4310 / joc.2012.v3.n4.a5
• Harper, L. (1966). Msgstr "Optimal numrering och isoperimetriska problem i grafer" . Journal of Combinatorial Theory . 1 (3): 385–393. doi : 10.1016 / S0021-9800 (66) 80059-5 .
• Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and complete problems to proper interval charts with small cliques", SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137 / s0097539793258143
• Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr (1997). "En approximationsalgoritm för bandbreddsproblemet på täta grafer" . Elektroniskt kollokvium om beräkningskomplexitet . 4 (17).

externa länkar

• Minsta bandbreddsproblem , i: Pierluigi Crescenzi och Viggo Kann (red.), Ett kompendium av NP-optimeringsproblem. Åtkomst 26 maj 2010.