Træ nedbrydning

I grafteori er trænedbrydning en kortlægning af en graf til et træ , der kan bruges til at bestemme træbredden af en graf og fremskynde løsningen af visse beregningsproblemer på grafer.

Inden for maskinlæring kaldes en trænedbrydning også et krydsningstræ , et kliktræ eller et nabotræ . Trænedbrydning spiller en vigtig rolle i problemer som probabilistisk inferens , at finde gyldige værdier , DBMS-forespørgselsoptimering og matrixnedbrydning .

Begrebet trænedbrydning blev oprindeligt foreslået af Halin [1] . Det blev senere genopdaget af Robertson og Seymour [2] og siden da er konceptet blevet undersøgt af mange andre forfattere [3] .

Definition

Intuitivt repræsenterer trænedbrydning hjørnerne af en given graf G som undertræer af et træ på en sådan måde, at grafens hjørner kun støder op, når de tilsvarende undertræer skærer hinanden. Så danner G en undergraf af undertræets skæringsgraf . Den komplette skæringsgraf er en akkordgraf .

Hvert undertræ forbinder et grafens toppunkt til et sæt træknuder. For at definere dette formelt, vil vi repræsentere hver træknude som et sæt af knudepunkter forbundet med det. Så for en given graf G = ( V , E ) er trænedbrydningen et par ( X , T ), hvor X = { X 1 , ..., X n } er en familie af delmængder af mængden V , og T er et træ, hvis noder er delmængder X i , der opfylder følgende egenskaber: [4]

Unionen af alle mængder X i er lig med V . Ethvert toppunkt på grafen er således forbundet med mindst én knude i træet.
For enhver kant ( v , w ) af grafen er der en delmængde X i , der indeholder både v og w . Hjørnepunkter er således kun tilstødende i en graf, hvis de svarer til undertræer, der har en fælles knude.
Hvis X i og X j indeholder v , så indeholder alle knudepunkter Xk i træet i den (unikke) sti mellem X i og Xj også v . Det vil sige, at knudepunkterne forbundet med toppunktet v danner en forbundet delmængde i T. Denne egenskab kan formuleres tilsvarende - hvis , og er noder, og er på vej fra til , så . $X_{i}$ $X_{j}$ $X_{k}$ $X_{k}$ $X_{i}$ $X_{j}$ ${\displaystyle X_{i}\cap X_{j}\subseteq X_{k))$

Trænedbrydningen af en graf er langt fra enestående. For eksempel indeholder en triviel trænedbrydning alle hjørnerne af grafen ved rodknuden.

En trænedbrydning, hvor træet er en sti , kaldes stinedbrydning, og træbredden af denne specielle slags trænedbrydning er kendt som stibredde .

En trænedbrydning ( X , T = ( I , F )) med træbredde k er jævn hvis for alle og for alle [5] . $i\in I:|X_{i}|=k+1$ $(i,j)\in F:|X_{i}\cap X_{j}|=k$

Træbredde

Bredden af et trænedbrydning er størrelsen af dets største sæt X i uden enhed. Træets bredde tw( G ) af G er minimumsbredden blandt alle mulige nedbrydninger af G . I denne definition er størrelsen af det største sæt reduceret med én for at gøre træets arboreale bredde lig med én. Træbredden kan bestemmes ud fra andre strukturer end trænedbrydning. Dette inkluderer akkordtællinger , torner og havne .

At bestemme om træbredden af en given graf G ikke overstiger k er et NP-komplet problem [6] . Men hvis k er en fast konstant, kan en graf med træbredde k genkendes, og en trænedbrydning af bredde k kan bygges i lineær tid [5] . Løbetiden for denne algoritme afhænger eksponentielt af k .

Dynamisk programmering

I begyndelsen af 1970'erne blev det bemærket, at problemer fra en stor klasse af kombinatoriske optimeringsproblemer på grafer kan løses effektivt ved hjælp af ikke-seriel dynamisk programmering , hvis grafen har en afgrænset dimension [7] , en træbredderelateret parameter. Senere opdagede nogle forfattere uafhængigt i slutningen af 1980'erne [8] , at mange algoritmiske NP-komplette problemer for vilkårlige grafer kan løses effektivt ved hjælp af dynamisk programmering for grafer med begrænset træbredde ved hjælp af trænedbrydning af disse grafer.

Forestil dig som et eksempel problemet med at finde det største uafhængige sæt på en graf med træbredde k . For at løse dette problem vælger vi først en trænedbrydningsnode som rod (vilkårligt). For en trænedbrydningsknude Xi , lad D i være foreningen af mængderne Xj nedarvet fra Xi . For en uafhængig mængde S ⊂ X i , lad A ( S , i ) angive størrelsen af den største uafhængige delmængde I af D i således at I ∩ X i = S . Tilsvarende, for et tilstødende par af noder X i og X j med X i længere fra roden end X j og et uafhængigt sæt S ⊂ X i ∩ X j , lad B ( S , i , j ) angive størrelsen af den største uafhængig delmængde I i D i sådan at I ∩ X i ∩ X j = S . Vi kan beregne disse værdier A og B ved at gå i træet fra bunden til toppen:

A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\right)

B(S,i,j)=\max _{S'\subset X_{i} \top S=S'\cap X_{j}}A(S',i)

Hvor summen i formlen for overtages knudepunktets efterkommere . $A(S,i)$ $X_{i}$

Ved hver knude eller kant er der højst 2k sæt S , for hvilke disse værdier skal beregnes, så i det tilfælde, hvor k er en konstant, tager alle beregninger konstant tid pr. kant eller knude. Størrelsen af det største uafhængige sæt er den største værdi, der er gemt i rodnoden, og selve det største uafhængige sæt kan findes (som det er standard i dynamisk programmering) ved at spore disse lagrede værdier tilbage, begyndende med den største værdi. I grafer over afgrænset træbredde kan problemet med at finde det største uafhængige sæt således løses i lineær tid. Lignende algoritmer kan anvendes til mange andre grafproblemer.

Denne dynamiske programmeringstilgang anvendes inden for maskinlæring ved hjælp af artikulationstræalgoritmen til at udbrede tillid på grafer med begrænset træbredde. Tilgangen spiller også en nøglerolle i algoritmerne til at beregne træbredden og opbygge en trænedbrydning. Typisk har sådanne algoritmer et første trin, der tilnærmer træets bredde og konstruerer en trænedbrydning med denne omtrentlige bredde, og det andet trin bruger dynamisk programmering på den resulterende trænedbrydning til at beregne den nøjagtige værdi af træbredden [5] .

Se også

Blackberry and Harbor , to slags strukturer, der kan bruges som et alternativ til trænedbrydning til at bestemme træbredden af en graf
Grengrafnedbrydning , en nært beslægtet struktur, hvis bredde er lineært relateret til træets bredde
Dekomponeringsmetode .

Noter

↑ Halin, 1976 .
↑ Robertson, Seymour, 1984 .
↑ Diestel, 2005 , s. 354-355.
↑ Diestel, 2005 , s. afsnit 12.3.
↑ 1 2 3 Bodlaender, 1996 .
↑ Arnborg, Corneil, Proskurowski, 1987 .
↑ Bertelé, Brioschi, 1972 .
↑ Arnborg, Proskurowski, 1989 ; Bern, Lawler, Wong, 1987 ; Bodlaender, 1988 .

Litteratur

S. Arnborg, D. Corneil, A. Proskurowski. Kompleksiteten ved at finde indlejringer i et k -træ // SIAM Journal om matrixanalyse og applikationer. - 1987. - T. 8 , no. 2 . — S. 277–284 . - doi : 10.1137/0608024 . .
S. Arnborg, A. Proskurowski. Lineære tidsalgoritmer for NP-hårde problemer begrænset til partielle k - træer // Diskret anvendt matematik. - 1989. - T. 23 , no. 1 . — S. 11–24 . - doi : 10.1016/0166-218X(89)90031-0 . .
MW Bern, EL Lawler, AL Wong. Lineær-tidsberegning af optimale undergrafer af nedbrydelige grafer // Journal of Algorithms. - 1987. - T. 8 , no. 2 . — S. 216–235 . - doi : 10.1016/0196-6774(87)90039-3 . .
Umberto Bertele, Francesco Brioschi. Ikke-seriel dynamisk programmering. - Academic Press, 1972. - ISBN 0-12-093450-7 . .
Hans L. Bodlaender. Proc. 15. internationale kollokvium om automater, sprog og programmering. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Forelæsningsnotater i datalogi). - doi : 10.1007/3-540-19488-6_110 . .
Hans L. Bodlaender. En lineær tidsalgoritme til at finde træ-nedbrydninger af lille træbredde // SIAM Journal on Computing. - 1996. - T. 25 , no. 6 . - S. 1305-1317 . - doi : 10.1137/S0097539793251219 . .
Reinhard Diestel. grafteori. — 3. - Springer , 2005. - ISBN 3-540-26182-6 . .
Rudolf Halin. S -funktioner til grafer // Journal of Geometry. - 1976. - T. 8 . — S. 171–186 . - doi : 10.1007/BF01917434 . .
Neil Robertson, Paul D. Seymour. Graph minor III: Planar tree-width // Journal of Combinatorial Theory, Series B. - 1984. - V. 36 , no. 1 . — s. 49–64 . - doi : 10.1016/0095-8956(84)90013-3 . .