Décomposition arborescente

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Définition[modifier | modifier le code]

Exemple de décomposition arborescente.

É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.

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

Utilisations[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : 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).

Bibliographie[modifier | modifier le code]

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