Trädnedbrytning

I grafteorin är trädnedbrytning en kartläggning av en graf till ett träd som kan användas för att bestämma trädbredden på en graf och påskynda lösningen av vissa beräkningsproblem på grafer.

Inom området för maskininlärning kallas en trädsönderdelning också ett korsningsträd , ett klickträd eller ett angränsande träd . Trädsönderdelning spelar en viktig roll i problem som probabilistisk slutledning , att hitta giltiga värden , optimering av DBMS-förfrågningar och matrisupplösning .

Begreppet trädnedbrytning föreslogs ursprungligen av Halin [1] . Det återupptäcktes senare av Robertson och Seymour [2] och sedan dess har konceptet studerats av många andra författare [3] .

Definition

Intuitivt representerar trädsönderdelning hörnen i en given graf G som underträd till ett träd på ett sådant sätt att grafens hörn ligger intill endast när motsvarande underträd skär varandra. Sedan bildar G en subgraf av underträdets skärningsgraf . Den fullständiga skärningsgrafen är en kordalgraf .

Varje underträd länkar en grafvertex till en uppsättning trädnoder. För att definiera detta formellt kommer vi att representera varje trädnod som en uppsättning hörn associerade med den. Sedan för en given graf G = ( V , E ) är trädsönderdelningen ett par ( X , T ), där X = { X 1 , ..., X n } är en familj av delmängder av mängden V , och T är ett träd vars noder är delmängder X i som uppfyller följande egenskaper: [4]

  1. Unionen av alla mängder X i är lika med V . Sålunda är varje vertex i grafen ansluten till åtminstone en nod i trädet.
  2. För valfri kant ( v , w ) av grafen finns det en delmängd Xi som innehåller både v och w . Alltså är hörn intilliggande i en graf endast om de motsvarar underträd som har en gemensam nod.
  3. Om Xi och Xj innehåller v , så innehåller alla noder Xk i trädet i den (unika) banan mellan Xi och Xj också v . Det vill säga, noderna associerade med vertex v bildar en ansluten delmängd i T . Den här egenskapen kan formuleras på samma sätt - om , och är noder, och är på väg från till , då .

Trädnedbrytningen av en graf är långt ifrån unik. Till exempel innehåller en trivial trädupplösning alla hörn i grafen vid rotnoden.

En trädnedbrytning där trädet är en bana kallas vägnedbrytning, och trädbredden för denna speciella typ av trädnedbrytning kallas vägbredd .

En trädsönderdelning ( X , T = ( I , F )) med trädbredd k är jämn om för alla och för alla [5] .

Träets bredd

Bredden på ett trädnedbrytning är storleken på dess största uppsättning X i utan enhet. Trädbredden tw( G ) av G är den minsta bredden bland alla möjliga nedbrytningar av G . I denna definition reduceras storleken på den största uppsättningen med en för att göra trädets trädbredd lika med en. Trädbredden kan bestämmas från andra strukturer än trädnedbrytning. Detta inkluderar ackordsräkningar , tortorn och hamnar .

Att bestämma om trädbredden för en given graf G inte överstiger k är ett NP-komplett problem [6] . Men om k är en fast konstant kan en graf med trädbredden k kännas igen och en trädsönderdelning av bredden k kan byggas i linjär tid [5] . Körtiden för denna algoritm beror exponentiellt på k .

Dynamisk programmering

I början av 1970-talet märktes det att problem från en stor klass av kombinatoriska optimeringsproblem på grafer kan lösas effektivt med hjälp av icke-seriell dynamisk programmering , om grafen har en avgränsad dimension [7] , en trädbreddsrelaterad parameter. Senare upptäckte några författare oberoende i slutet av 1980 -talet [8] att många algoritmiska NP-kompletta problem för godtyckliga grafer kan lösas effektivt med dynamisk programmering för grafer med begränsad trädbredd genom att använda träduppdelning av dessa grafer.

Som ett exempel, föreställ dig problemet med att hitta den största oberoende uppsättningen på en graf med trädets bredd k . För att lösa detta problem väljer vi först en trädnedbrytningsnod som rot (godtyckligt). För en trädnedbrytningsnod Xi , låt Di vara föreningen av mängderna Xj som ärvts från Xi . För en oberoende mängd S  ⊂  X i , låt A ( S , i ) beteckna storleken på den största oberoende delmängden I av D i så att I  ∩  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 från roten än X j och en oberoende mängd S  ⊂  X i  ∩  X j , låt B ( S , i , j ) beteckna storleken på den största oberoende delmängd I i D i så att I  ∩  X i  ∩  X j  =  S . Vi kan beräkna dessa värden A och B genom att gå i trädet från botten till toppen:

Där summan i formeln för tas över nodens ättlingar .

Vid varje nod eller kant finns det högst 2k uppsättningar S för vilka dessa värden behöver beräknas, så att i fallet där k är en konstant tar alla beräkningar konstant tid per kant eller nod. Storleken på den största oberoende uppsättningen är det största värdet som lagras i rotnoden, och den största oberoende uppsättningen i sig kan hittas (som är standard i dynamisk programmering) genom att spåra tillbaka dessa lagrade värden, med början med det största värdet. Sålunda, i grafer över avgränsad trädbredd, kan problemet med att hitta den största oberoende uppsättningen lösas i linjär tid. Liknande algoritmer är tillämpliga på många andra grafproblem.

Denna dynamiska programmeringsmetod tillämpas inom området maskininlärning med hjälp av artikulationsträdalgoritmen för att sprida förtroende på grafer med begränsad trädbredd. Tillvägagångssättet spelar också en nyckelroll i algoritmerna för att beräkna trädets bredd och bygga en trädnedbrytning. Typiskt har sådana algoritmer ett första steg som approximerar trädets bredd och konstruerar en trädnedbrytning med denna ungefärliga bredd, och det andra steget använder dynamisk programmering på den resulterande trädsönderdelningen för att beräkna det exakta värdet av trädbredden [5] .

Se även

Anteckningar

  1. ↑ Halin, 1976 .
  2. ↑ Robertson, Seymour, 1984 .
  3. ↑ Diestel, 2005 , sid. 354–355.
  4. ↑ Diestel, 2005 , sid. avsnitt 12.3.
  5. ↑ 1 2 3 Bodlaender, 1996 .
  6. ↑ Arnborg, Corneil, Proskurowski, 1987 .
  7. ↑ Bertelé, Brioschi, 1972 .
  8. ↑ Arnborg, Proskurowski, 1989 ; Bern, Lawler, Wong, 1987 ; Bodlaender, 1988 .

Litteratur