Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Décomposition arborescente
Résumé
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.
É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 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 , une décomposition arborescente de est un couple , où est une famille de sous-ensembles de sommets de , et est un arbre dont les nœuds sont étiquetés par ces sous-ensembles , tels que :
l'union de tous les de est égale à ;
pour toute arête de , il existe un nœud de l'arbre qui contient v et w ;
si et contiennent un même sommet v, alors tous les nœuds de sur le chemin entre et contiennent v.
Cette dernière condition est équivalente au fait que tous les nœuds de l'arbre contenant un nœud v de induisent un sous-arbre de .
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.