Mesure numérique de la proximité d'un graphe non orienté à un arbre, définie comme le minimum, parmi toutes les décompositions arborescentes, du maximum des tailles des sacs moins un ; une faible largeur d'arbre signifie que le graphe peut être organisé par petits ensembles de sommets qui se chevauchent et sont disposés en arbre.

Principe

Organiser le graphe par un arbre de sacs de sommets chevauchants et prendre la plus grande taille de sac comme métrique de coût ; la minimisation de ce maximum caractérise la plus petite taille d'interactions locales nécessaires pour reconstruire la structure globale.

Démonstration

Un arbre ou une forêt a largeur d'arbre 1 (les sacs contiennent au plus deux sommets) ; un chemin simple a largeur d'arbre 1, un cycle a largeur d'arbre 2, et le graphe complet à n sommets a largeur d'arbre n−1 ; de nombreux algorithmes de programmation dynamique s'exécutent en temps exponentiel en la largeur d'arbre mais polynomial en la taille du graphe.

Mauvaise application

Confondre degré maximum, arboricité ou largeur de chemin (pathwidth) avec la largeur d'arbre et supposer qu'un faible degré maximal implique une faible largeur d'arbre, ou appliquer des algorithmes dépendant de la largeur d'arbre sans produire une décomposition arborescente valide de largeur bornée.

Conséquence

Quand un graphe a une largeur d'arbre bornée, de nombreux problèmes difficiles au sens général (coloration, variantes d'Hamiltonien, satisfaction de contraintes) admettent des solutions en temps fixé-parameterisé ou polynomial paramétrées par la largeur d'arbre ; la théorie structurelle des graphes fournit des théorèmes de décomposition et de mineurs liés à la largeur d'arbre.

Inversion

Le point de vue inverse concerne les graphes à grande largeur d'arbre (expanders, mineurs denses) qui résistent à une décomposition en petits sacs et présentent des propriétés de connectivité globale ; une largeur d'arbre élevée rend les approches locales et arborescentes moins efficaces mais signale une richesse combinatoire.

Limite

Défini pour des graphes non orientés via des décompositions arborescentes ; des extensions existent pour graphes orientés et hypergraphes mais exigent des formules différentes ; la largeur d'arbre est invariante par mineur mais ne mesure pas la parcimonie (sparsity) au sens large et diffère d'invariants apparentés comme le pathwidth ou le tree-depth.

Tension sémantique

Tension avec le pathwidth, le tree-depth et les mesures de parcimonie : le pathwidth impose une forme plus linéaire de décomposition, le tree-depth mesure une complexité de type hauteur, et la densité/arboricité caractérisent la distribution des arêtes ; chacun saisit des contraintes structurelles différentes.

Synthèse

La largeur d'arbre condense la complexité globale d'un graphe dans la taille des morceaux locaux chevauchants organisés en arbre : construire une décomposition arborescente minimisant la taille maximale des sacs ; une valeur petite indique que de nombreux problèmes globaux se réduisent à un raisonnement local en structure arborescente.