Nella teoria dei grafi , una decomposizione ad albero o decomposizione ad albero (in inglese : tree-decomposition ) consiste in una scomposizione di un grafo in separatori (sottoinsiemi di vertici la cui rimozione rende il grafo disconnesso), connesso in un albero . Questa scomposizione permette di definire un'altra nozione importante, la larghezza dell'albero o la larghezza dell'albero (treewidth).
Questo metodo è stato proposto da Paul Seymour e Neil Robertson come parte della loro teoria sui minatori di un grafo . È noto anche nell'apprendimento automatico , dove si parla di albero di giunzione , in particolare nell'algoritmo dell'albero di giunzione .
Dato un grafo G, una decomposizione ad albero di G è un albero i cui nodi sono sottoinsiemi di vertici del grafo come:
In generale, ci sono diverse decomposizioni ad albero.
Formalmente, dato un grafo , una decomposizione ad albero di è una coppia , dove è una famiglia di sottoinsiemi di vertici di , ed è un albero i cui nodi sono etichettati da questi sottoinsiemi , come ad esempio:
Quest'ultima condizione equivale al fatto che tutti i nodi dell'albero contenente un nodo v di inducono un sottoalbero di .
Questo metodo si applica quando si cerca di risolvere un problema di ottimizzazione combinatoria il cui grafico è parte dei dati. L'idea è di risolvere il problema iniziale su ciascuno dei sottoinsiemi della scomposizione, quindi unire i risultati nell'albero utilizzando metodi di programmazione dinamica . Il metodo è applicabile solo per problemi molto specifici, ad esempio la colorazione dei grafici.
Il minimo tra tutti i guasti, la dimensione a meno che uno dei sottoinsiemi più grandi sia chiamato larghezza dell'albero ( larghezza dell'albero ) del grafico. Tale valore determina quindi l'interesse ad utilizzare il metodo della scomposizione. La larghezza dell'albero può essere un buon parametro per la complessità parametrizzata di alcuni problemi.
Quando l'albero è composto da un solo percorso , si parla di scomposizione lineare ( path-decomposition ) e larghezza lineare ( albero) ( pathwidth ).