Largeur de l'arbre

La largeur de l'arbre est un terme de la théorie des graphes . Il dit à quel point un graphique ressemble à un arbre . Étant donné que de nombreux algorithmes fonctionnent efficacement sur des arbres (ou des décompositions d'arbres) qui ne le font pas sur des graphes généraux, il est intéressant de connaître la largeur de l'arbre. Un terme connexe est la longueur du chemin .

Le terme a été introduit en 1972 par Umberto Bertelè et Francesco Brioschi, indépendamment de Rudolf Halin en 1976 et de nouveau indépendamment de Neil Robertson et Paul Seymour en 1984.

Définition formelle

Une décomposition arborescente de est une paire , où est un arbre et est une famille de sous-ensembles de l'ensemble de nœuds du graphe tels que: ${\ displaystyle G = (V, E)}$${\ displaystyle (X, T)}$${\ displaystyle T = (I, F)}$${\ displaystyle X = \ {X_ {i} | i \ in I \}}$ ${\ displaystyle V}$

• ${\ displaystyle \ bigcup _ {i \ in I} X_ {i} = V}$.
• Il y en a un avec pour tous les bords .${\ displaystyle (v, w) \ dans E}$${\ displaystyle i \ in I}$${\ displaystyle v, w \ in X_ {i}}$
• Le suivant applique à tous : s'il est sur le chemin de la dans , puis .${\ Displaystyle i, j, k \ in I}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle k}$${\ displaystyle T}$${\ displaystyle X_ {i} \ cap X_ {k} \ subseteq X_ {j}}$

La largeur de l' arbre de la décomposition d'arbre de est définie comme et la largeur de l' arbre d' un graphique est définie comme la plus petite largeur d'arbre de toutes les décompositions d'arbre de . ${\ displaystyle (X, T)}$${\ displaystyle G}$${\ displaystyle \ max _ {i \ in I} | X_ {i} | -1}$${\ displaystyle G}$${\ displaystyle G}$

La soustraction de 1 entraîne la largeur de l'arbre à 1 si et seulement s'il y a un arbre (sans cette soustraction, les arbres auraient une largeur d'arbre 2). ${\ displaystyle G}$${\ displaystyle G}$

Explication

Nous distribuons les nœuds de G sur des sacs (en anglais: seaux ou sacs) disposés dans un arbre, les règles suivantes s'appliquent:

• Chaque nœud est dans au moins une poche${\ displaystyle V}$
• Les deux nœuds d'extrémité de chaque bord sont ensemble dans au moins une poche
• Pour chaque nœud , les poches qui contiennent forment un sous-arbre${\ displaystyle v}$${\ displaystyle v}$

caractéristiques

complexité

Le problème de décision de savoir si pour un graphe donné G et une variable k donnée la largeur de l'arbre de G est au plus k est NP-complet . Les graphes avec une largeur d'arbre limitée par une constante k peuvent cependant être reconnus en temps linéaire. Le temps d'exécution de cet algorithme dépend linéairement du nombre de nœuds de G et exponentiellement de k .

Barrières

Les largeurs d'arbre suivantes s'appliquent:

• Chaque arbre avec au moins 2 nœuds a une largeur d'arbre d'exactement 1.
• Chaque graphe circulaire avec au moins 3 nœuds a une largeur d'arbre d'exactement 2.
• Un graphe sans arêtes (y compris un arbre avec 1 nœud) a une largeur d'arbre d'exactement 0.
• Les graphes en série parallèle ont une largeur d'arbre d'au plus 2.
• Les halingraphes ont une largeur d' arbre ne dépassant pas 3.
• La largeur de l'arbre des graphes planaires n'est pas limitée par une constante. Cela ressort clairement de l'exemple du - graphe en grille . Ceux-ci ont une largeur d'arbre de . La largeur de l'arbre des graphes planaires avec mais noeud a été limitée.${\ displaystyle (n \ fois n)}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle 3.182 \ cdot {\ sqrt {n}}}$
• La largeur de l'arbre d'un graphique est au plus 1 plus petite que sa plus grande clique .

Littérature

• Reinhard Diestel: théorie des graphes . 5e édition. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-96134-004-0 , 10e Mineurs, p. 287-330 . 
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: des algorithmes exacts pour des problèmes de graphes difficiles . Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-642-04499-1 . 
• Hans L. Bodlaender: Tractabilité à paramètres fixes de Treewidth et Pathwidth . Dans: Bodlaender HL, Downey R., Fomin FV, Marx D. (Eds.): The Multivariate Algorithmic Revolution and Beyond . LNCS 7370. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-30890-1 , pp. 196-227 , doi : 10.1007 / 978-3-642-30891-8_12 . 

Preuve individuelle

1. ↑ Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, appelé Dimension
2. ↑ Halin, fonctions S pour graphes, J. Geom., 8, 1976, 171-186
3. ^ Robertson, Seymour: Graph mineurs III: Planar tree-width, Journal of Combinatorial Theory, Série B, Volume 36, 1984, pp.49-64
4. ↑ S. Arnborg; D. Corneil; A. Proskurowski: Complexité de trouver des plongements dans un k-tree. SIAM Journal on Matrix Analysis and Applications, 8 (2) 1987, p. 277-284
5. ↑ Hans L. Bodlaender: Un algorithme de temps linéaire pour trouver des décompositions d'arbres de petite largeur d'arbre. SIAM Journal on Computing, 25 (6) 1996, pp. 1305-1317
6. ↑ Fedor V. Fomin, Dimitrios M. Thilikos: Nouvelles limites supérieures sur la décomposabilité des graphes planaires . Dans: Journal of Graph Theory . ruban 51 , non. 1 , 2006, p. 53–81 , doi : 10.1002 / jgt.20121 .