Ê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 GraphSearch.
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.
Concepts associés (7)
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.
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.
Lexique de la théorie des graphes
NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.
Cours associés (3)
MATH-381: Mathematical logic
Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.
CS-250: Algorithms
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
MATH-683: Fine-grained and parameterized complexity
The classical distinction between polynomial time solvable and NP-hard problems is often too coarse. This course covers techniques for proving more fine-grained lower and upper bounds on complexity of
Séances de cours associées (4)
Théorie des graphiques et flux réseau
Introduit la théorie des graphiques, les flux de réseau et les lois de conservation des flux avec des exemples pratiques et des théorèmes.
Élimination des bords et orientation dans les graphiques
Couvre l'élimination des bords et l'orientation dans les graphiques, y compris les tests de premier ordre et l'orientation logique.
Réseaux : Structure et propriétés
Explore la structure et les propriétés des réseaux, y compris les réseaux de rencontres et de protéines, les effets de petit monde, les hubs et les propriétés sans échelle.