Décomposition arborescente

En théorie des graphes, une décomposition arborescente ou décomposition en arbre (en anglais : tree-decomposition) consiste en une décomposition d'un graphe en séparateurs (sous-ensembles de sommets dont la suppression rend le graphe non connexe), connectés dans un arbre. Cette décomposition permet de définir une autre notion importante, la largeur arborescente ou largeur d'arbre (treewidth).

Cette méthode a été proposée par Paul Seymour et Neil Robertson dans le cadre de leur théorie sur les mineurs d'un graphe. Elle est aussi connue en apprentissage automatique, où l'on parle d'arbre de jonction, notamment dans l'algorithme de l'arbre de jonction.

Définition

Exemple de décomposition arborescente.

Étant donné un graphe G, une décomposition arborescente de G est un arbre dont les nœuds sont des sous-ensembles de sommets du graphe tels que :

• les sous-ensembles couvrent les sommets de G ;
• pour toute arête $(v,w)$ dans le graphe G, il existe un nœud de l'arbre qui contient v et w ;
• Pour tout sommet v, les nœuds contenant v forment un sous-arbre.

En général, il existe plusieurs décompositions arborescentes.

Formellement, étant donné un graphe $G=(V,E)$, une décomposition arborescente de $G$ est un couple $(X,T)$, où $X=\{X_{1},\ldots ,X_{n}\}$ est une famille de sous-ensembles de sommets de $V$, et $T$ est un arbre dont les nœuds sont étiquetés par ces sous-ensembles $X_{i}$, tels que :

• l'union de tous les $X_{i}$ de $X$ est égale à $V$ ;
• pour toute arête $(v,w)$ de $E$, il existe un nœud $X_{i}$ de l'arbre $T$ qui contient v et w ;
• si $X_{i}$ et $X_{j}$ contiennent un même sommet v, alors tous les nœuds $X_{z}$ de $T$ sur le chemin entre $X_{i}$ et $X_{j}$ contiennent v.

Cette dernière condition est équivalente au fait que tous les nœuds $X_{i}$ de l'arbre $T$ contenant un nœud v de $G$ induisent un sous-arbre de $T$.

Utilisations

Cette méthode s'applique lorsque l'on cherche à résoudre un problème d'optimisation combinatoire dont le graphe fait partie de la donnée. L'idée est de résoudre le problème initial sur chacun des sous-ensembles de la décomposition, puis de fusionner les résultats dans l'arbre à l'aide de méthodes de programmation dynamique. La méthode ne s'applique que pour des problèmes bien particuliers, la coloration de graphes, par exemple.

Largeur arborescente

Le minimum, parmi toutes les décompositions, de la taille moins un du plus grand sous-ensemble est appelée largeur arborescente (treewidth) du graphe. Cette valeur détermine donc l'intérêt d'utiliser la méthode de décomposition. La largeur d'arbre peut être un bon paramètre pour la complexité paramétrée de certains problèmes.

Lorsque l'arbre n'est constitué que d'un chemin, on parle de décomposition linéaire (path-decomposition) et de largeur (arborescente) linéaire (pathwidth).

Article lié

• Roncier

Bibliographie

• Bruno Courcelle, Décompositions arborescentes (Cours Master) (lire en ligne)