Largeur arborescente

En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières, notamment en utilisant la décomposition arborescente. Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée. Dans beaucoup d'applications, les graphes ont des largeurs arborescentes petites, comme les réseaux sociaux. Informellement, étant donné un graphe non orienté G {\displaystyle G} , une décomposition arborescente de G {\displaystyle G} est un arbre T {\displaystyle T} dont les nœuds sont annotés par des sous-ensembles de sommets de G {\displaystyle G} , qui vérifient les conditions suivantes : Formellement, étant donné un graphe non orienté G = ( V , E ) {\displaystyle G=(V,E)} , une décomposition arborescente de G {\displaystyle G} est un couple ( T , λ ) {\displaystyle (T,\lambda )} où T {\displaystyle T} est un arbre, et λ {\displaystyle \lambda } est une fonction associant à chaque nœud t {\displaystyle t} de T {\displaystyle T} un sous-ensemble λ ( t ) ⊆ V {\displaystyle \lambda (t)\subseteq V} , qui vérifie les conditions suivantes : Tout graphe a au moins une décomposition arborescente, par exemple celle où l'arbre T {\displaystyle T} a un seul sommet t {\displaystyle t} et où λ ( t ) = V {\displaystyle \lambda (t)=V} . Dans ce cas, tous les sommets et les arêtes du graphe sont couvertes dans λ ( t ) {\displaystyle \lambda (t)} , et la condition sur les chemins est trivialement satisfaite. Cependant, cette décomposition n'est pas unique. Plus généralement, tout graphe G = ( V , E ) {\displaystyle G=(V,E)} admet une infinité de décompositions arborescentes : on peut par exemple choisir n'importe quel arbre T {\displaystyle T} , et définir λ {\displaystyle \lambda } par λ ( t ) = V {\displaystyle \lambda (t)=V} pour tout nœud t {\displaystyle t} . La largeur arborescente d'une décomposition arborescente ( T , λ ) {\displaystyle (T,\lambda )} est le cardinal de la plus grande étiquette moins un.