Trænedbrydning

I grafteori består en trænedbrydning eller trænedbrydning (på engelsk  : trænedbrydning ) af en nedbrydning af en graf i separatorer (delmængder af hjørner, hvis fjernelse gør den frakoblede graf), forbundet i et træ . Denne nedbrydning gør det muligt at definere et andet vigtigt begreb, den træet bredde eller træ bredde (treewidth).

Denne metode blev foreslået af Paul Seymour og Neil Robertson som en del af deres teori om minearbejdere i en graf . Det er også kendt inden for maskinlæring , hvor vi taler om et krydsetræ , især i krydstræalgoritmen .

Definition

Givet en graf G, er en trænedbrydning af G et træ, hvis knudepunkter er delmængder af hjørner af grafen, såsom:

• delmængderne dækker hjørnerne af G;
• for enhver kant i grafen G findes der en knude på træet, der indeholder v og w  ;(v,w){\ displaystyle (v, w)}
• For ethvert toppunkt v danner noderne, der indeholder v, et undertræ.

Generelt er der flere trænedbrydninger.

Formelt, givet en graf , er en trænedbrydning af et par , hvor er en familie af delmængder af hjørner af , og er et træ, hvis knudepunkter er mærket af disse delmængder , såsom: G=(V,E){\ displaystyle G = (V, E)}G{\ displaystyle G}(x,T){\ displaystyle (X, T)}x={x1,...,xikke}{\ displaystyle X = \ {X_ {1}, \ ldots, X_ {n} \}}V{\ displaystyle V}T{\ displaystyle T}xjeg{\ displaystyle X_ {i}}

• foreningen af alle af er lig med  ;xjeg{\ displaystyle X_ {i}}x{\ displaystyle X}V{\ displaystyle V}
• for enhver kant af eksisterer der en node af træet, der indeholder v og w  ;(v,w){\ displaystyle (v, w)}E{\ displaystyle E}xjeg{\ displaystyle X_ {i}}T{\ displaystyle T}
• hvis og indeholde den samme knude v , så alle noder for på stien mellem og indeholde v .xjeg{\ displaystyle X_ {i}}xj{\ displaystyle X_ {j}}xz{\ displaystyle X_ {z}}T{\ displaystyle T}xjeg{\ displaystyle X_ {i}}xj{\ displaystyle X_ {j}}

Denne sidste betingelse er ækvivalent med det faktum, at alle knudepunkterne af træet indeholder en knude v af fremkalde en undertræ af . xjeg{\ displaystyle X_ {i}}T{\ displaystyle T}G{\ displaystyle G}T{\ displaystyle T}

Anvendelser

Denne metode gælder, når man søger at løse et kombinatorisk optimeringsproblem, hvis graf er en del af dataene. Ideen er at løse det oprindelige problem på hver af delmængderne af nedbrydningen og derefter flette resultaterne ind i træet ved hjælp af dynamiske programmeringsmetoder . Metoden kan kun anvendes til meget specifikke problemer, f.eks. Farvning af grafer.

Træbredde

Den mindste blandt alle de opdelinger, størrelse medmindre en af de største delmængde kaldes treewidth ( treewidth ) af grafen. Denne værdi bestemmer derfor interessen ved at bruge nedbrydningsmetoden. Akselbredde kan være en god parameter til den parametriserede kompleksitet af nogle problemer.

Når træet kun består af en sti , taler vi om lineær nedbrydning ( sti-nedbrydning ) og lineær ( træ) bredde ( stivbredde ).

Relateret artikel

• Bramble

Bibliografi

• Bruno Courcelle , trænedbrydninger (Master Course) ( læs online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">