Trebredde
I grafteori og i teoretisk datateknologi , de tre bredde eller tre bredde av en kurve ( treewidth ) er et tall som intuitivt mål på hvorvidt det er i nærheten av et tre. Det kan defineres på flere måter , Spesielt ved å bruke trenedbrytning .
Ofte er et enkelt algoritmisk problem på trær faktisk enkelt på grafer som ser ut som trær. Dermed brukes denne parameteren ofte i grafalgoritmer, spesielt for polynomiske tilnærmingsskjemaer og parametrisert kompleksitet . I mange applikasjoner har grafer små trebredder , for eksempel sosiale nettverk.
Definisjon
Med trenedbrytning
Definisjon av en trenedbrytning
Uformelt, gitt en ikke-rettet graf , er en trenedbrytning av et tre hvis noder er merket av delmengder av hjørner av , som tilfredsstiller følgende betingelser:
G{\ displaystyle G}
G{\ displaystyle G}
T{\ displaystyle T}
G{\ displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
- hvert toppunkt vises på etiketten til en node av ;G{\ displaystyle G}
T{\ displaystyle T}![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- for en hvilken som helst kant av finnes det en node hvis etikett inneholder og ;{v,w}{\ displaystyle \ {v, w \}}
G{\ displaystyle G}
T{\ displaystyle T}
v{\ displaystyle v}
w{\ displaystyle w}![w](https://wikimedia.org/api/rest_v1/media/math/render/svg/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6)
- for ethvert toppunkt på , knutepunktene til treet som inneholder, danner et sammenkoblet undertre av .v{\ displaystyle v}
G{\ displaystyle G}
v{\ displaystyle v}
T{\ displaystyle T}![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
Formelt sett, gitt en ikke-rettet graf , er en trenedbrytning et par som er et tre, og er en funksjon som knytter seg til hver node i en delmengde , som oppfyller følgende betingelser:
G=(V,E){\ displaystyle G = (V, E)}
G{\ displaystyle G}
(T,λ){\ displaystyle (T, \ lambda)}
T{\ displaystyle T}
λ{\ displaystyle \ lambda}
t{\ displaystyle t}
T{\ displaystyle T}
λ(t)⊆V{\ displaystyle \ lambda (t) \ subseteq V}![{\ displaystyle \ lambda (t) \ subseteq V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adcbfd59d2b00e387421b35556fc5637bc08db5e)
- For ethvert toppunkt eksisterer det en node på treet slik at . Denne betingelsen tilsvarer å pålegge at fagforeningen er lik .v∈V{\ displaystyle v \ in V}
t{\ displaystyle t}
T{\ displaystyle T}
v∈λ(t){\ displaystyle v \ in \ lambda (t)}
⋃t∈Tλ(t){\ displaystyle \ bigcup _ {t \ in T} \ lambda (t)}
V{\ displaystyle V}![V](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
- For en hvilken som helst kant eksisterer det en node av slik at .{v,w}∈E{\ displaystyle \ {v, w \} \ i E}
t{\ displaystyle t}
T{\ displaystyle T}
{v,w}⊆λ(t){\ displaystyle \ {v, w \} \ subseteq \ lambda (t)}![{\ displaystyle \ {v, w \} \ subseteq \ lambda (t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/068e47231380a11bc264c5a3ff208f85f7d4d333)
- For ethvert toppunkt , danner nodene et tilkoblet undertre av . Denne tilstand utgjør imponerende at for alle noder , og av hvilke inneholder de samme toppunktet (det vil si og ), alle nodene av på den ene enkle kjede mellom og også tilfredsstille .v∈V{\ displaystyle v \ in V}
{t∈T∣v∈λ(t)}{\ displaystyle \ {t \ in T \ mid v \ in \ lambda (t) \}}
T{\ displaystyle T}
t{\ displaystyle t}
t′{\ displaystyle t '}
T{\ displaystyle T}
v{\ displaystyle v}
v∈λ(t){\ displaystyle v \ in \ lambda (t)}
v∈λ(t′){\ displaystyle v \ in \ lambda (t ')}
t"{\ displaystyle t ''}
T{\ displaystyle T}
t{\ displaystyle t}
t′{\ displaystyle t '}
v∈λ(t"){\ displaystyle v \ in \ lambda (t '')}![{\ displaystyle v \ in \ lambda (t '')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/044112092b2d905c7896b399c463dc08a8982afa)
Enhver graf har minst en trenedbrytning, for eksempel den der treet har et enkelt toppunkt og hvor . I dette tilfellet er alle hjørner og kanter i grafen dekket av , og tilstanden på stiene er trivielt tilfredsstilt. Denne nedbrytningen er imidlertid ikke unik. Mer generelt innrømmer enhver graf en uendelig trenedbrytning: vi kan for eksempel velge hvilket som helst tre , og definere ved for hvilken som helst node .
T{\ displaystyle T}
t{\ displaystyle t}
λ(t)=V{\ displaystyle \ lambda (t) = V}
λ(t){\ displaystyle \ lambda (t)}
G=(V,E){\ displaystyle G = (V, E)}
T{\ displaystyle T}
λ{\ displaystyle \ lambda}
λ(t)=V{\ displaystyle \ lambda (t) = V}
t{\ displaystyle t}![t](https://wikimedia.org/api/rest_v1/media/math/render/svg/65658b7b223af9e1acc877d848888ecdb4466560)
Definisjon av trebredde
Trebredden til en trenedbrytning er kardinalen til den største etiketten minus en. Formelt handler det om . I eksempelet på figuren, alle etikettene er av kardinal 3, derfor treet bredden på dette treet nedbrytning er 2. treet bredde ( treewidth ) av en graf G er den minste av de tre bredde blant alle tre oppdelinger av denne kurve.
(T,λ){\ displaystyle (T, \ lambda)}
(makst∈T|λ(t)|)-1{\ displaystyle \ left (\ max _ {t \ in T} \ left | \ lambda (t) \ right | \ right) -1}![{\ displaystyle \ left (\ max _ {t \ in T} \ left | \ lambda (t) \ right | \ right) -1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63ce3e6f4acc311ecdfc6ec86b058df6729e3268)
Hvis vi vurderer en triviell trenedbryting der nodene er merket med settet med alle hjørner i grafen, ser vi at en hvilken som helst graf med hjørner har en trebredde på maksimalt. På den annen side, hvis er et tre, hvis vi bygger ved å følge strukturen til , kan vi få en trenedbrytning der hver etikett inneholder nøyaktig to elementer, derfor med bredde 1.
V{\ displaystyle V}
ikke{\ displaystyle n}
ikke-1{\ displaystyle n-1}
G{\ displaystyle G}
T{\ displaystyle T}
G{\ displaystyle G}
G{\ displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Via trianguleringer
For enhver graf betegner vi rekkefølgen til den største klikken på . De tre Bredden av en kurve som er den minste verdi tatt av , blant alle triangulering av .
H{\ displaystyle H}
ω(H){\ displaystyle \ omega (H)}
H{\ displaystyle H}
G{\ displaystyle G}
ω(H)-1{\ displaystyle \ omega (H) -1}
H{\ displaystyle H}
G{\ displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Eksempler
Trær har trebredde 1. Størrelsen n- klikken har trebredden n-1 . Det firkantede rutenettet av størrelse n har en akselbredde lik n .
Algoritmiske aspekter
Beregning av trebredde
Beregningen av trebredde er NP-vanskelig . Imidlertid, hvis det er løst, er det en lineær algoritme for å bestemme om trebredden til en graf er . Avhengigheten av algoritmens utførelsestid er imidlertid eksponentiell. For noen bestemte klasser av grafer, beregnes trebredden på polynomisk tid (trær, triangulerte grafer, etc.).
k{\ displaystyle k}
k{\ displaystyle k}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Algoritmiske bruksområder
Mange problemer med NP-vanskelige grafer kan generelt løses i polynomial tid hvis vi begrenser oss til grafer med avgrenset trebredde. Det er derfor en god parameter for kompleksiteten som er parameterisert . Hvis problemet kan uttrykkes i andreordens monadiske logikk , sier Courcelles teorem at det da kan løses i lineær tid (men konstanten er en eksponensiell vending som gjør algoritmen utilgjengelig generelt).
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
For eksempel kan det maksimale stabile problemet for plane grafer løses i polynomtid for en avgrenset trebredde (vi tar deretter denne bredden som en konstant), noe som gjør det mulig å oppnå et tilnærmingsskjema i polynomtid når vi ikke begrenser bredde.
Koblinger med triangulerte grafer
Konseptet med trenedbrytning har en veldig sterk kobling med trekantede grafer . For det første er trebredden til en triangulert graf H lik størrelsen på det største klikket minus ett. For det andre kan verdien beregnes ved hjelp av en lineær algoritme hvis grafen H er triangulert. I litteraturen av operasjonsanalyse , algoritmer for beregning av tre-bredde for en graf G ofte søke å bestemme triangulert grafen H av lavere verdi, som inneholder G .
χ(H){\ displaystyle \ chi (H)}
χ(H){\ displaystyle \ chi (H)}
χ(H){\ displaystyle \ chi (H)}![\ chi (H)](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe218f5c37b6b6cb34dab8a0ca17ea34fa0a3421)
Tilhørende grafparametere
Trebredden kan knyttes til andre grafparametere, for eksempel degenerering eller bramble .
En variant for dirigerte grafer er definert, den er null på asykliserte grafer .
Bibliografi
Virker
Artikler
Merknader og referanser
-
(in) David P. Williamson og David B. Shmoys , Design of approximation algoritms , Cambridge University Press ,2010, 500 s. ( online presentasjon , les online ) , kap. 10.2 ("Det maksimale uavhengige settproblemet i plane grafer")s. 272.
-
Uli Wagner, “ Grafer og algoritmer: Avanserte emner trebredde ” .
-
Arnborg, Corneil og Proskurowski 1987 .
-
Bruno Courcelle , “ Den monadiske andreordens logikk av grafer. I. Gjenkjennelige sett med endelige grafer ”, Informasjon og beregning , vol. 85, n o 1,1 st mars 1990, s. 12–75 ( DOI 10.1016 / 0890-5401 (90) 90043-H , leses online , åpnet 3. desember 2017 )
-
David P. Williamson og David B. Shmoys , Design of Approximation Algorithms ,
2010, s. 273.
-
Thor Johnson, Neil Robertson , Paul D. Seymour og Robin Thomas, " Directed Tree-Width ", J. Comb. Teori, ser. B , vol. 8, n o 1,
2001, s. 138-154 ( DOI 10.1006 / jctb.2000.2031 ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">