Voir la source de Largeur arborescente

En [[théorie des graphes]] et en [[informatique théorique]], la '''largeur arborescente''' ou '''largeur d'arbre''' d'un graphe ('''''{{Langue|en|treewidth}}''''' en anglais) est un nombre qui, intuitivement,  mesure s'il est proche d'un arbre<ref>{{Approximation (Williamson et Shmoys)|numéro chapitre=10.2|titre chapitre=The maximum independent set problem in planar graphs}} p. 272.</ref>. Elle peut être définie de plusieurs manières{{Lesquelles}}, 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{{Référence nécessaire|date=14 juin 2018}}, comme par exemple les réseaux sociaux.

== Définition ==

=== Avec la décomposition arborescente ===
[[Image:Tree decomposition.svg|thumb|240px|Exemple d'un graphe G et d'une décomposition arborescente de G.]]

==== Définition d'une décomposition arborescente ====
Informellement, étant donné un [[graphe non orienté]] <math>G</math>, une décomposition arborescente de <math>G</math> est un [[arbre (graphe)|arbre]] <math>T</math> dont les nœuds sont annotés par des [[sous-ensembles]] de sommets de <math>G</math>, qui vérifient les conditions suivantes :
* chaque sommet de <math>G</math> apparaît dans l'étiquette d'un nœud de <math>T</math> ;
* pour toute arête <math>\{v, w\}</math> de <math>G</math>, il existe un nœud de <math>T</math> dont l'étiquette contient <math>v</math> et <math>w</math> ;
* pour tout sommet <math>v</math> de <math>G</math>, les nœuds de l'arbre qui contiennent <math>v</math> forment un [[sous-arbre]] [[graphe connexe|connexe]] de <math>T</math>.

Formellement, étant donné un graphe non orienté <math>G = (V, E)</math>, une décomposition arborescente de <math>G</math> est un couple <math>(T, \lambda)</math> où <math>T</math> est un arbre, et <math>\lambda</math> est une [[fonction (mathématiques)|fonction]] associant à chaque nœud <math>t</math> de <math>T</math> un sous-ensemble <math>\lambda(t) \subseteq V</math>, qui vérifie les conditions suivantes :
* Pour tout sommet <math>v \in V</math>, il existe un nœud <math>t</math> de l'arbre <math>T</math> tel que <math>v \in \lambda(t)</math>. Cette condition revient à imposer que l'union <math>\bigcup_{t \in T} \lambda(t)</math> soit égale à <math>V</math>.
* Pour toute arête <math>\{v, w\} \in E</math>, il existe un nœud <math>t</math> de <math>T</math> tel que <math>\{v, w\} \subseteq \lambda(t)</math>.
* Pour tout sommet <math>v \in V</math>, les nœuds <math>\{t \in T \mid v \in \lambda(t)\}</math> forment un sous-arbre connexe de <math>T</math>. Cette condition revient à imposer que, pour tous nœuds <math>t</math> et <math>t'</math> de <math>T</math> qui contiennent un même sommet <math>v</math> (c'est-à-dire <math>v \in \lambda(t)</math> et <math>v 
\in \lambda(t')</math>), tous les nœuds <math>t''</math> de <math>T</math> sur l'unique [[chaîne (théorie des graphes)|chaîne]] simple entre <math>t</math> et <math>t'</math> satisfont également <math>v \in \lambda(t'')</math>.

Tout graphe a au moins une décomposition arborescente, par exemple celle où l'arbre <math>T</math> a un seul sommet <math>t</math> et où <math>\lambda(t) = V</math>. Dans ce cas, tous les sommets et les arêtes du graphe sont couvertes dans <math>\lambda(t)</math>, et la condition sur les chemins est trivialement satisfaite. Cependant, cette décomposition n'est pas unique. Plus généralement, tout graphe <math>G = (V, E)</math> admet une infinité de décompositions arborescentes : on peut par exemple choisir n'importe quel arbre <math>T</math>, et définir <math>\lambda</math> par <math>\lambda(t) = V</math> pour tout nœud <math>t</math>.

==== Définition de la largeur arborescente ====
La largeur arborescente d'une décomposition arborescente <math>(T, \lambda)</math> est le cardinal de la plus grande étiquette moins un. Formellement, il s'agit de <math>\left(\max_{t \in T} \left| \lambda(t) \right| \right) - 1</math>. Dans l'exemple de la figure, toutes les étiquettes sont de cardinal 3, donc la largeur arborescente de cette décomposition arborescente est 2. La '''largeur arborescente''' (''{{Langue|en|treewidth}}'') d'un graphe G est le minimum de la largeur arborescente parmi toutes les décompositions arborescentes de ce graphe.

Si l'on considère une décomposition arborescente triviale où les nœuds sont étiquetés par l'ensemble <math>V</math> de tous les sommets du graphe, on constate que tout graphe avec <math>n</math> sommets a une largeur arborescente de <math>n - 1</math> au plus. En revanche, si <math>G</math> est un arbre, si on construit <math>T</math> en suivant la structure de <math>G</math>, on peut obtenir une décomposition arborescente de <math>G</math> où chaque étiquette contient exactement deux éléments, donc de largeur 1.

=== Via les triangulations ===

Pour tout graphe <math>H</math>, on note <math>\omega(H)</math> l'[[Lexique_de_la_th%C3%A9orie_des_graphes#O|ordre]] de la plus grande [[clique]] de <math>H</math>.
La '''largeur arborescente''' d'un graphe <math>G</math> est la plus petite valeur prise par <math>\omega(H)-1</math>, parmi toutes les [[Triangulation_de_graphe| triangulations]] <math>H</math> de <math>G</math>.

== Exemples ==
Les arbres ont largeur d'arbre 1. La [[clique (théorie des graphes)|clique]] de taille ''n'' a largeur d'arbre ''n-1''.
La grille carrée de taille ''n'' a une [[largeur d'arbre]] égale à ''n''<ref>{{lien web|url=https://www.ti.inf.ethz.ch/ew/lehre/GA10/lec-treewidth-new.pdf|titre=Graphs & Algorithms: Advanced Topics Treewidth|auteur=Uli Wagner}}.</ref>.

== Aspects algorithmiques ==
=== Calcul de la largeur arborescente ===
Le calcul de la largeur arborescente est [[NP-difficile]]<ref>{{Harvsp|Arnborg|Corneil|Proskurowski|1987}}.</ref>. Néanmoins, si <math>k</math> est fixé, il existe un algorithme linéaire pour déterminer si la largeur arborescente d'un graphe est <math>k</math>. La dépendance en <math>k</math> du temps d'exécution de l'algorithme est cependant exponentielle. Pour certaines classes particulières de graphes, calculer la largeur arborescente se fait en [[Notations de Landau|temps polynomial]] (arbres, graphes triangulés, etc.).

=== Utilisations en algorithmique === 

De nombreux problèmes de graphes NP-difficiles dans le cas général peuvent être résolus en temps polynomial si on se restreint aux graphes de largeur arborescente bornée. C'est donc un bon paramètre pour la [[complexité paramétrée]]. Si le problème est exprimable en [[logique monadique du second ordre]], le [[théorème de Courcelle]]<ref>{{Article|prénom1=Bruno|nom1=Courcelle|titre=The monadic second-order logic of graphs. I. Recognizable sets of finite graphs|périodique=Information and Computation|volume=85|numéro=1|date=1990-03-01|doi=10.1016/0890-5401(90)90043-H|lire en ligne=http://www.sciencedirect.com/science/article/pii/089054019090043H|consulté le=2017-12-03|pages=12–75}}</ref> énonce qu'il peut alors être résolu en temps linéaire (mais la constante est une tour d'exponentielles en <math>k</math> qui rend l'algorithme inapplicable en général).

Par exemple, le [[problème du stable maximum]] pour des [[graphe planaire|graphes planaires]] peut-être résolu en temps polynomial pour une largeur arborescente bornée (on prend alors cette largeur comme une constante)<ref>
{{ouvrage
 | titre = The Design of Approximation Algorithms
 | nom1 = Williamson
 | prénom1 = David P. | lien auteur1 =David P. Williamson
 | nom2 = Shmoys
 | prénom2 = David B.
 | année = 2010
 | passage = 273 }}.</ref>, ce qui permet d'obtenir un schéma d'approximation en temps polynomial quand on ne contraint pas la largeur.

=== Liens avec les graphes triangulés ===

Le concept de décomposition arborescente a un lien très fort avec les [[Triangulation de graphe|graphes triangulés]]. Premièrement, la largeur arborescente d'un graphe triangulé ''H'' est égale à la taille <math>\chi(H)</math> de sa plus grande [[clique (théorie des graphes)|clique]] moins un. Deuxièmement, la valeur <math>\chi(H)</math> peut être calculée à l'aide d'un [[Algorithmique|algorithme]] linéaire si le graphe ''H'' est triangulé. Dans la littérature de [[recherche opérationnelle]], les algorithmes de calcul de la largeur arborescente d'un graphe ''G'' cherchent souvent à déterminer le graphe triangulé ''H'' de plus petite valeur <math>\chi(H)</math> qui contient ''G''.

== Paramètres de graphes associés ==
La largeur arborescente peut-être reliée à d'autres paramètres de graphes, comme la [[Dégénérescence (théorie des graphes)|dégénérescence]] ou le [[roncier (théorie des graphes)|roncier]].

Une variante pour les graphes orientés a été définie, elle vaut zéro sur les [[graphe orienté acyclique|graphes orientés acycliques]]<ref>
{{article
 | auteur1    = Thor Johnson|auteur2= [[Neil Robertson (mathématicien)|Neil Robertson]]|auteur3= [[Paul D. Seymour]] |auteur4 = Robin Thomas
 | titre     = Directed Tree-Width
 | périodique  = J. Comb. Theory, Ser. B
 | volume    = 8| numéro    = 1
 | passage     = 138-154
 | année      = 2001
 | doi       = 10.1006/jctb.2000.2031}}.</ref>.

== Bibliographie ==
=== Ouvrages ===
* {{Approximation (Williamson et Shmoys)}}
* {{article
 | langue        = en
 | auteur1       = Hans L. Bodlaender
 | titre         = A tourist guide through treewidth
 | journal       = Technical report RUU-CS
 | année         = 1993
 | volume        = 92
 | lire en ligne = http://igitur-archive.library.uu.nl/math/2006-1214-203348/bodlaender_92_a%20tourist%20guide.pdf
 | id            = 
}}

=== Articles ===
* {{article
 | nom1 = Arnborg | prénom1 = S.
 | nom2 = Corneil | prénom2 = D. 
 | nom3 = Proskurowski | prénom3 = A.
 | titre = Complexity of finding embeddings in a ''k''-tree
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 8 | numéro = 2 | année = 1987 | pages = 277–284 | doi = 10.1137/0608024}}

== Notes et références ==
{{Références}}

== Article lié ==
* [[Largeur de clique]]
{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Concept en théorie des graphes]]
[[Catégorie:Invariant de graphe]]