Trädnedbrytning - Tree decomposition

En graf med åtta hörn och en trädnedbrytning av den på ett träd med sex noder. Varje grafkant ansluter två hörn som är listade tillsammans vid någon trädnod och varje grafhörn är listad vid noderna i ett angränsande underträd av trädet. Varje trädnod listar högst tre hörn, så bredden på denna sönderdelning är två.

I grafteori , en träd nedbrytning är en kartläggning av en kurva i ett träd som kan användas för att definiera treewidth av grafen och påskynda lösa vissa beräkningsproblem i diagrammet.

Trädnedbrytning kallas också korsningsträd , klickträd eller sammanfogningsträd ; de spelar en viktig roll i problem som probabilistisk slutsats , tillfredsställelse av begränsningar , optimering av frågor och matrisnedbrytning .

Begreppet trädnedbrytning introducerades ursprungligen av Rudolf Halin  ( 1976 ). Senare upptäcktes den av Neil Robertson och Paul Seymour  ( 1984 ) och har sedan dess studerats av många andra författare.

Definition

Intuitivt representerar en trädnedbrytning vertikalerna i en given graf G som underträd av ett träd, på ett sådant sätt att vertikaler i den angivna grafen endast angränsar när motsvarande underträd skär varandra. Sålunda, G bildar en subgraf av skärnings graf av underträden. Hela korsningsdiagrammet är ett ackorddiagram .

Varje underträd associerar ett diagramverktyg med en uppsättning trädnoder. För att definiera detta formellt representerar vi varje trädnod som den uppsättning vertikaler som är associerade med den. Med tanke på ett diagram G = ( V , E ) är ett trädnedbrytning ett par ( X , T ), där X = { X ₁ , ..., X _n } är en familj av delmängder (ibland kallade påsar ) av V , och T är ett träd, vars noder är de undergrupper X _i , som uppfyller följande egenskaper:

1. Förbundet av alla uppsättningar X _jag lika V . Det vill säga att varje grafhörn är associerat med minst en trädnod.
2. För varje kant ( v , w ) i grafen, finns det en delmängd X _jag som innehåller både v och w . Det vill säga, hörn är intill i diagrammet endast när motsvarande underträd har en nod gemensamt.
3. Om X _i och X _j båda innehåller en vertex v , sedan alla noder X _k av trädet i (unikt) bana mellan X _i och X _j innehålla v samt. Dvs noderna associerade med vertex v bilda en ansluten delmängd av T . Detta är också känt som koherens eller egenskapen löpande korsning . Det kan likvärdigt anges att om , och är noder, och är på väg från till , då .${\ displaystyle X_ {i}}$${\ displaystyle X_ {j}}$${\ displaystyle X_ {k}}$${\ displaystyle X_ {k}}$${\ displaystyle X_ {i}}$${\ displaystyle X_ {j}}$${\ displaystyle X_ {i} \ cap X_ {j} \ subseteq X_ {k}}$

Trädens sönderdelning av en graf är långt ifrån unik; Till exempel innehåller en trivial trädnedbrytning alla kurvor i grafen i dess enda rotnod.

En trädnedbrytning där det underliggande trädet är ett kurvdiagram kallas en vägnedbrytning, och breddparametern härledd från dessa speciella typer av trädnedbrytningar kallas vägbredd .

En trädnedbrytning ( X , T = ( I , F )) av trebredd k är jämn , om för alla och för alla . ${\ displaystyle i \ i I: | X_ {i} | = k + 1}$${\ displaystyle (i, j) \ i F: | X_ {i} \ cap X_ {j} | = k}$

Det minsta antalet träd i ett träd nedbrytning är träd antal av G.

Trebredd

Två olika trädnedbrytningar av samma diagram

Den bredden av ett träd nedbrytning är storleken på den största uppsättningen X _I minus ett. Den treewidth tw ( G ) hos en graf G är den minsta bredden bland alla möjliga trädsönderdelningar av G . I denna definition minskas storleken på den största uppsättningen med en för att göra trädets bredd lika med ett. Trebredd kan också definieras från andra strukturer än trädnedbrytningar, inklusive ackorddiagram , brambles och tillflyktsorter .

Det är NP-komplett för att avgöra om en given graf G har högst tre bredd för en given variabel k . Men när k är någon fast konstant kan graferna med trebredd k kännas igen, och en bredd k trädnedbrytning konstrueras för dem, i linjär tid. Tidsberoendet för denna algoritm av k är exponentiellt.

Dynamisk programmering

I början av 1970-talet observerades att en stor klass av kombinatoriska optimeringsproblem som definierats i grafer effektivt kunde lösas genom icke-seriell dynamisk programmering så länge som grafen hade en begränsad dimension , en parameter relaterad till trebredd. Senare observerade flera författare oberoende, i slutet av 1980-talet, att många algoritmiska problem som är NP-kompletta för godtyckliga grafer kan lösas effektivt genom dynamisk programmering för grafer med avgränsad träbredd med hjälp av trädnedbrytningarna i dessa grafer.

Tänk som ett exempel på problemet med att hitta den maximala oberoende uppsättningen i en graf med trebredd k . För att lösa detta problem, välj först en av noderna i trädnedbrytningen för att vara roten, godtyckligt. För en nod X _I i trädet nedbrytning, låt D _jag vara Unionen uppsättningar X _j fallande från X _i . För en oberoende uppsättning S  ⊂  X _i , låt A ( S , i ) beteckna storleken på den största oberoende delmängd jag av D _jag så att jag  ∩  X _i  =  S . På liknande sätt, för ett angränsande par av noder X _i och X _j , med X _i längre bort från roten av trädet än X _j , och en oberoende uppsättning S  ⊂  X _i  ∩  X _j , låt B ( S , i , j ) betecknar storleken på den största oberoende delmängd i av D _jag så att jag  ∩  X _jag  ∩  X _j  =  S . Vi kan beräkna dessa A- och B- värden genom en nedifrån och upp-genomgång av trädet:

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

${\ displaystyle B (S, i, j) = \ max _ {S '\ subset X_ {i} \ ovanpå S = S' \ cap X_ {j}} A (S ', i)}$

där summan i beräkningen är över barnen till noden . ${\ displaystyle A (S, i)}$${\ displaystyle X_ {i}}$

Vid varje nod eller kant finns det högst 2 ^k uppsättningar S som vi behöver beräkna dessa värden för, så om k är konstant så tar hela beräkningen konstant tid per kant eller nod. Storleken på den maximala oberoende uppsättningen är det största värdet som lagras vid rotnoden, och den maximala oberoende uppsättningen kan hittas (som standard i dynamiska programmeringsalgoritmer) genom att spåra igenom dessa lagrade värden med utgångspunkt från detta största värde. Således, i grafer över avgränsad trebredd, kan det maximala oberoende inställningsproblemet lösas i linjär tid. Liknande algoritmer gäller för många andra grafproblem.

Denna dynamiska programmeringsmetod används vid maskininlärning via korsningsträdalgoritmen för trosutbredning i grafer med begränsad träbredd. Det spelar också en nyckelroll i algoritmer för beräkning av träbredden och konstruktion av trädnedbrytning: typiskt har sådana algoritmer ett första steg som approximerar träbredden, konstruerar en trädnedbrytning med denna ungefärliga bredd och sedan ett andra steg som utför dynamisk programmering i ungefärlig trädnedbrytning för att beräkna det exakta värdet av trädbredden.

Se även

• Brambles och skatteparadis  - två typer av strukturer som kan användas som ett alternativ till träd nedbrytning i att definiera treewidth av en graf.
• Grennedbrytning  - En nära besläktad struktur vars bredd ligger inom en konstant breddfaktor.
• Sönderdelningsmetod  - Sönderdelning av träd används i sönderdelningsmetod för att lösa problem med begränsningstillfredsställelse.

Anteckningar

Referenser