Décomposition arborescente

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

É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 ${\displaystyle (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 ${\displaystyle G=(V,E)}$, une décomposition arborescente de ${\displaystyle G}$ est un couple ${\displaystyle (X,T)}$, où ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$ est une famille de sous-ensembles de sommets de ${\displaystyle V}$, et ${\displaystyle T}$ est un arbre dont les nœuds sont étiquetés par ces sous-ensembles ${\displaystyle X_{i}}$, tels que :

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

Cette dernière condition est équivalente au fait que tous les nœuds ${\displaystyle X_{i}}$ de l'arbre ${\displaystyle T}$ contenant un nœud v de ${\displaystyle G}$ induisent un sous-arbre de ${\displaystyle 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)

• Portail de l'informatique théorique