Rozklad stromu

V teorii grafů je dekompozice stromu mapování grafu do stromu , které lze použít k určení šířky stromu grafu a urychlení řešení určitých výpočetních problémů na grafech.

V oblasti strojového učení se dekompozice stromu také nazývá junction tree , clique tree nebo sousedící strom . Dekompozice stromu hraje důležitou roli v problémech, jako je pravděpodobnostní inference , hledání platných hodnot , optimalizace dotazů DBMS a dekompozice matice .

Koncept rozkladu stromů původně navrhl Halin [1] . Později jej znovu objevili Robertson a Seymour [2] a od té doby se tímto konceptem zabývalo mnoho dalších autorů [3] .

Definice

Dekompozice stromu intuitivně představuje vrcholy daného grafu G jako podstromy stromu tak, že vrcholy grafu sousedí pouze tehdy, když se odpovídající podstromy protínají. Potom G tvoří podgraf grafu průniku podstromu . Úplný průsečíkový graf je tětivový graf .

Každý podstrom spojuje vrchol grafu se sadou uzlů stromu. Abychom to formálně definovali, budeme reprezentovat každý uzel stromu jako sadu vrcholů s ním spojených. Pak pro daný graf G = ( V , E ) je stromový rozklad dvojice ( X , T ), kde X = { X 1 , ..., X n } je rodina podmnožin množiny V a T je strom, jehož uzly jsou podmnožiny X i splňující následující vlastnosti: [4]

  1. Sjednocení všech množin X i je rovno V . Jakýkoli vrchol grafu je tedy připojen alespoň k jednomu uzlu stromu.
  2. Pro jakoukoli hranu ( v , w ) grafu existuje podmnožina X i obsahující v i w . Vrcholy tedy sousedí v grafu pouze tehdy, pokud odpovídají podstromům, které mají společný uzel.
  3. Pokud X i a X j obsahují v , pak všechny uzly X k stromu na (unikátní) cestě mezi X i a X j obsahují také v . To znamená, že uzly spojené s vrcholem v tvoří spojenou podmnožinu v T . Tuto vlastnost lze formulovat ekvivalentně — if , a are nodes, and is on the way from to , then .

Stromový rozklad grafu není zdaleka ojedinělý. Například triviální rozklad stromu obsahuje všechny vrcholy grafu v kořenovém uzlu.

Dekompozice stromu, ve které je strom cestou , se nazývá dekompozice cesty a šířka stromu tohoto speciálního druhu dekompozice stromu se nazývá šířka cesty .

Rozklad stromu ( X , T = ( I , F )) o šířce stromu k je hladký , pokud pro všechny a pro všechny [5] .

Šířka dřeva

Šířka rozkladu stromu je velikost jeho největší množiny X i bez jednoty. Šířka stromu tw( G ) G je minimální šířka mezi všemi možnými rozklady G. V této definici je velikost největší sady zmenšena o jednu, aby se stromová šířka stromu rovnala jedné. Šířku stromu lze určit z jiných struktur, než je rozklad stromu. To zahrnuje akordické počty , ostružiní a přístavy .

Určení, zda šířka stromu daného grafu G nepřesahuje k , je NP-úplný problém [6] . Pokud je však k pevná konstanta, lze rozpoznat graf se šířkou stromu k a sestavit stromový rozklad o šířce k v lineárním čase [5] . Doba běhu tohoto algoritmu závisí exponenciálně na k .

Dynamické programování

Na počátku 70. let bylo zjištěno, že problémy z velké třídy kombinatorických optimalizačních problémů na grafech lze efektivně řešit pomocí nesériového dynamického programování , pokud má graf omezenou dimenzi [7] , parametr související se šířkou stromu. Později někteří autoři nezávisle na sobě koncem 80. let zjistili [8] , že mnoho algoritmických NP-úplných problémů pro libovolné grafy lze efektivně řešit pomocí dynamického programování pro grafy s omezenou šířkou stromu pomocí stromové dekompozice těchto grafů.

Jako příklad si představme problém nalezení největší nezávislé množiny na grafu o šířce stromu k . K vyřešení tohoto problému nejprve vybereme jeden uzel rozkladu stromu jako kořen (libovolně). Pro uzel rozkladu stromu X i nechť D i je sjednocením množin X j zděděných z X i . Pro nezávislou množinu S  ⊂  X i označme A ( S , i ) velikost největší nezávislé podmnožiny I z D i takovou, že I  ∩  X i  =  S . Podobně pro sousední dvojici uzlů X i a X j s X i dále od kořene než X j a nezávislou množinu S  ⊂  X i  ∩  X j označme B ( S , i , j ) velikost největšího nezávislá podmnožina I v D i taková, že I  ∩  X i  ∩  X j  =  S . Tyto hodnoty A a B můžeme vypočítat procházením stromu zdola nahoru:

Kde součet ve vzorci pro je převzat z potomků uzlu .

Na každém uzlu nebo hraně existuje nejvýše 2k množin S , pro které je třeba tyto hodnoty vypočítat, takže v případě, že k je konstanta, všechny výpočty zaberou na hranu nebo uzel konstantní čas. Velikost největší nezávislé množiny je největší hodnota uložená v kořenovém uzlu a samotnou největší nezávislou množinu lze nalézt (jak je v dynamickém programování standardem) zpětným sledováním těchto uložených hodnot, počínaje největší hodnotou. V grafech s omezenou šířkou stromu lze tedy problém najít největší nezávislou množinu řešit v lineárním čase. Podobné algoritmy jsou použitelné pro mnoho dalších problémů s grafy.

Tento přístup dynamického programování je aplikován v oblasti strojového učení pomocí algoritmu artikulačního stromu k šíření důvěry v grafech s omezenou šířkou stromu. Tento přístup také hraje klíčovou roli v algoritmech pro výpočet šířky stromu a sestavení rozkladu stromu. Typicky mají takové algoritmy první krok, který aproximuje šířku stromu a vytváří rozklad stromu s touto přibližnou šířkou, a druhý krok používá dynamické programování na výsledném rozkladu stromu k výpočtu přesné hodnoty šířky stromu [5] .

Viz také

Poznámky

  1. ↑ Halin, 1976 .
  2. ↑ Robertson, Seymour, 1984 .
  3. ↑ Diestel, 2005 , str. 354–355.
  4. ↑ Diestel, 2005 , str. oddíl 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 .

Literatura