Ê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
Largeur arborescente
Résumé
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. Dans beaucoup d'applications, les graphes ont des largeurs arborescentes petites, comme par exemple les réseaux sociaux.
Informellement, étant donné un graphe non orienté , une décomposition arborescente de est un arbre dont les nœuds sont annotés par des sous-ensembles de sommets de , qui vérifient les conditions suivantes :
chaque sommet de apparaît dans l'étiquette d'un nœud de ;
pour toute arête de , il existe un nœud de dont l'étiquette contient et ;
pour tout sommet de , les nœuds de l'arbre qui contiennent forment un sous-arbre connexe de .
Formellement, étant donné un graphe non orienté , une décomposition arborescente de est un couple où est un arbre, et est une fonction associant à chaque nœud de un sous-ensemble , qui vérifie les conditions suivantes :
Pour tout sommet , il existe un nœud de l'arbre tel que . Cette condition revient à imposer que l'union soit égale à .
Pour toute arête , il existe un nœud de tel que .
Pour tout sommet , les nœuds forment un sous-arbre connexe de . Cette condition revient à imposer que, pour tous nœuds et de qui contiennent un même sommet (c'est-à-dire et ), tous les nœuds de sur l'unique chaîne simple entre et satisfont également .
Tout graphe a au moins une décomposition arborescente, par exemple celle où l'arbre a un seul sommet et où . Dans ce cas, tous les sommets et les arêtes du graphe sont couvertes dans , et la condition sur les chemins est trivialement satisfaite. Cependant, cette décomposition n'est pas unique.
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.