Arbre de Trémaux

Un article de Wikipédia, l'encyclopédie libre.

En théorie des graphes, un arbre de Trémaux, pour un graphe non orienté G, est un arbre couvrant de G, enraciné en l'un de ses sommets, avec la propriété que deux sommets qui sont voisins dans G sont reliés l'un à l'autre en tant qu'ascendant et descendant dans l'arbre.

Description générale[modifier | modifier le code]

Les arbres obtenus par un parcours en profondeur (en anglais depth-first search trees) et les chaînes hamiltoniennes sont des arbres de Trémaux. Les arbres de Trémaux doivent leur nom à Charles Pierre Trémaux[1], un ingénieur français du XIXe siècle qui a utilisé une sorte d'algorithme de parcours en profondeur comme stratégie pour résoudre des labyrinthes[2],[3]. Les arbres de Trémaux sont également été appelé arbres couvrants normaux, en particulier dans le contexte des graphes infinis[4].

Dans les graphes finis, bien que la recherche en profondeur soit intrinsèquement séquentielle, les arbres de Trémaux peuvent aussi être construits par un algorithme parallèle randomisé de la classe de complexité RNC. Ils peuvent être utilisés pour définir la profondeur d'arbre (en) d'un graphe et, dans le cadre du test de planarité gauche-droite, pour tester si un graphe est un graphe planaire.

Une caractérisation des arbres de Trémaux dans la logique monadique du second ordre sur les graphes permet de reconnaître efficacement les propriétés des graphes impliquant des orientations pour les graphes de largeur arborescente bornée en utilisant le théorème de Courcelle.

Les graphes infinis connexe ne possèdent pas tous des arbres de Trémaux, et les graphes qui en possèdent peuvent être caractérisés par leurs mineurs interdits. Un arbre de Trémaux existe dans chaque graphe connexe ayant un nombre dénombrable de sommets, même si une variante infinie de l'algorithme de parcours en profondeur ne parvient pas toujours à explorer chaque sommet du graphe. Dans un graphe infini, un arbre de Trémaux doit avoir exactement un chemin infini pour chaque bout du graphe, et l'existence d'un arbre Trémaux caractérise les graphes dont les complétions topologiques, formées en ajoutant un point à l'infini en tant que bout, sont des espaces métriques.

Exemple[modifier | modifier le code]

Dans le graphe ci-dessous, l'arbre formé des arêtes 1–3, 2–3 et 3–4 est un arbre de Trémaux lorsqu'il est enraciné au sommet 1 ou au sommet 2 : chaque arête du graphe appartient à l'arbre sauf l'arête 1–2 qui (pour ce choix de racine) relie une paire ancêtre-descendant.

En revanche, enraciner le même arbre au sommet 3 ou au sommet 4 produit un arbre enraciné qui n'est pas un arbre de Trémaux, car avec cette racine les sommets 1 et 2 ne sont plus ancêtres ou descendants l'un de l'autre.

Graphes finis[modifier | modifier le code]

Existence[modifier | modifier le code]

Tout graphe connexe non orienté fini possède au moins un arbre de Trémaux. On peut construire un tel arbre en effectuant un parcours en profondeur et en connectant chaque sommet (autre que le sommet de départ de la recherche) au sommet à partir duquel il a été découvert. L'arbre ainsi construit est appelé arbre de recherche en profondeur ou arbre de parcours en profondeur. Si u-v est une arête quelconque du graphe, et u est le premier des deux sommets atteints par la recherche, alors v doit appartenir au sous-arbre descendant de u dans l'arborescence de recherche en profondeur, car la recherche découvre nécessairement v durant l'exploration ce sous-arbre, soit à partir de u directement, soit à partir de l'un des sommets du sous-arbre. Chaque arbre de Trémaux fini peut être engendré comme un arbre de recherche en profondeur : si T est un arbre de Trémaux d'un graphe fini, une recherche en profondeur qui explore les enfants, dans T, d'un sommet avant d'explorer les autres sommets, construit T comme son arbre de recherche en profondeur.

Construction parallèle[modifier | modifier le code]

Trouver un arbre de Trémaux donné par un algorithme de recherche en profondeur, dans lequel les voisins de chaque sommet sont cherchés dans l'ordre de leur identité est un problème P-complet[5]. En revanche, il est possible de trouver un arbre de Trémaux différent par un algorithme parallèle randomisé, montrant que la construction des arbres de Trémaux appartient à la classe de complexité RNC[6] . En 1997, il était encore ouvert si la construction de l'arbre de Trémaux pouvait être réalisée par un algorithme parallèle déterministe dans la classe de complexité NC[7] .

Expression logique[modifier | modifier le code]

Il est possible d'exprimer la propriété qu'un ensemble T d'arêtes avec un choix de sommet racine r forme un arbre de Trémaux, dans la logique monadique de second ordre des graphes, et plus précisément dans la logique dite MSO2, qui permet la quantification à la fois sur les ensembles de sommets et les ensembles d'arêtes. Cette propriété peut être exprimée comme la conjonction des propriétés suivantes :

  • Le graphe est couvert par les arêtes de T. Cela peut être exprimé logiquement comme l'affirmation que, pour chaque sous-ensemble propre non vide des sommets du graphe, il existe une arête en T avec exactement un point d'extrémité dans ce sous-ensemble donné.
  • T est acyclique. Cela peut être exprimé logiquement comme l'affirmation qu'il n'existe pas de sous-ensemble non vide C de T pour lequel chaque sommet est incident à zéro ou à deux arêtes de C.
  • Chaque arête e qui n'est pas dans T relie une paire ancêtre-descendant de sommets en T. Cela est vrai lorsque les deux extrémités de e appartiennent à un chemin dans T. Cela peut être exprimé logiquement comme l'affirmation que, pour toute arête e, il existe un sous-ensemble P de T tel que exactement deux sommets, parmi lesquels r, sont incidents à une seule arête de P, et tels que les deux extrémités de e sont incident sur au moins une arête de P.

Une fois qu'un arbre de Trémaux a été identifié de cette manière, on peut décrire une orientation du graphe donné, également en logique monadique de second ordre, en spécifiant l'ensemble des arêtes orientés d'un sommet vers un sommet qui en est descendant dans l'arbre. Les arêtes ne figurant pas dans cet ensemble doivent être orientés dans l'autre direction. Cette technique permet de spécifier des propriétés de graphe impliquant des orientations en logique monadique du second ordre, ce qui permet de tester ces propriétés efficacement sur des graphes de largeur d'arbre bornée en utilisant le théorème de Courcelle[8].

Propriétés connexes[modifier | modifier le code]

Si un graphe a un chemin hamiltonien, alors ce chemin (enraciné à l'une de ses d'extrémités) est également un arbre de Trémaux. Les graphes non orientés pour lesquels chaque arbre Trémaux a cette forme sont les graphes cycle, les graphes complets et les graphes bipartis complets équilibrés[9].

Les arbres de Trémaux sont étroitement liés au concept de profondeur d'arbre. La profondeur d'arbre d'un graphe G peut être définie comme le plus petit nombre d tel que G puisse être plongé comme sous-graphe dans un graphe H qui a un arbre de Trémaux T de profondeur d . Une profondeur d'arbre bornée, dans une famille de graphes, équivaut à l'existence d'un chemin qui ne peut pas se produire en tant que mineur des graphes de la famille. De nombreux problèmes de calcul difficiles sur les graphes ont des algorithmes qui sont traitables en complexité paramétrée lorsqu'ils sont paramétrés par la profondeur d'arbre de leurs entrées[10].

Les arbres de Trémaux jouent également un rôle clé dans le critère de planarité de Fraysseix–Rosenstiehl pour tester si un graphe donné est planaire . Selon ce critère, un graphe G est planaire si et seulement si, pour un arbre Trémaux donné T de G, les arêtes restantes peuvent être placées de manière cohérente à gauche ou à droite de l'arbre, sous la contrainte qui que deux arêtes placées du même côté ne doivent pas se croiser[11],[12].

Graphes infinis[modifier | modifier le code]

Existence[modifier | modifier le code]

Les graphes infinis ne possèdent pas tous un arbre couvrant normal. Par exemple, un graphe complet sur un ensemble infini non dénombrable de sommets n'en possède pas : un arbre couvrant normal dans un graphe complet ne peut être qu'un chemin, mais un chemin n'a qu'un nombre dénombrable de sommets. Cependant, chaque graphe sur un ensemble dénombrable de sommets a un arbre couvrant normal[4].

Même dans les graphes dénombrables, une recherche en profondeur peut ne pas réussir à explorer le graphe tout entier[4], et chaque arbre couvrant normal ne peut pas être engendré par une recherche en profondeur d'abord: pour être un arbre de recherche en profondeur, un arbre couvrant normal dénombrable ne doit avoir qu'un seul chemin infini ou un seul nœud avec un nombre infini d'enfants (et pas les deux).

Mineurs[modifier | modifier le code]

Si un graphe infini G possède un arbre couvrant normal, il en est de même pour chaque mineur connexe de G. Il en résulte que les graphes qui ont des arbres couvrant normaux admettent une caractérisation par mineurs interdits. L'une des deux classes de mineurs interdits se compose de graphes bipartis dans lesquels une partie de la bipartition est dénombrable, l'autre partie est non dénombrable et chaque sommet a un degré infini. L'autre classe de mineurs interdits est constituée de certains graphes dérivés des arbres d'Aronszajn[13] .

Les détails de cette caractérisation dépendent du choix de l'axiomatisation de la théorie des ensembles utilisée pour formaliser les mathématiques. En particulier, dans les modèles de théorie des ensembles pour lesquels l'axiome de Martin est vrai et l'hypothèse du continu est fausse, la classe de graphes bipartis dans cette caractérisation peut être remplacée par un seul mineur interdit. Cependant, pour les modèles dans lesquels l'hypothèse du continu est vraie, cette classe contient des graphes qui sont incomparables pour l'ordre sur les mineurs[14].

Fins et espaces métrisables[modifier | modifier le code]

Les arbres couvrant normaux sont également étroitement liés aux fins dans un graphe infini : une bout est une classe d'équivalence de rayons, c'est-à-dire de chemins infinis, où deux rayons sont équivalents s'il existe un troisième rayon qui contient une infinité de sommets de chacun des deux autres. Intuitivement, un bout est une classe d'équivalence de chemins infinis qui vont en quelque sorte à l'infini dans la même direction. Si un graphe possède un arbre couvrant normal, cet arbre doit avoir exactement un chemin infini pour chacun des bouts du graphe.

Un graphe infini peut être utilisé pour former un espace topologique en considérant le graphe lui-même comme un complexe simplicial et en ajoutant un point à l'infini pour chaque bout du graphe. Avec cette topologie, un graphe possède un arbre couvrant normal si et seulement si son ensemble de sommets peut être décomposé en une union dénombrable d'ensembles fermés . De plus, cet espace topologique peut être représenté par un espace métrique si et seulement si le graphe possède un arbre couvrant normal[15].

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trémaux tree » (voir la liste des auteurs).
  1. ↑ D’après la base de données des anciens élèves de l’École polytechnique citée par Pierre Rosenstiehl dans Pierre Rosenstiehl, « Labyrinthes et fil d'Ariane », Images des Mathématiques,‎ (lire en ligne, consulté le ), Charles-Pierre Trémaux a vécu de 1859 à 1882. Ce n'est donc pas Pierre Trémaux, né le 20 juillet 1818 à Charrecey et mort le 12 mars 1895 à Tournus
  2. ↑ Shimon Even, Graph Algorithms, Cambridge University Press, , 2e éd., 46–48 p. (ISBN 978-0-521-73653-4, lire en ligne).
  3. ↑ Robert Sedgewick, Algorithms in C++ : Graph Algorithms, Pearson Education, , 3e éd., 149–157 p. (ISBN 978-0-201-36118-6, lire en ligne).
  4. ↑ a b et c Lajos Soukup, « Infinite combinatorics: from finite to infinite », Horizons of combinatorics, Berlin, Springer, vol. 17,‎ , p. 189–213 (ISBN 978-3-540-77199-9, DOI 10.1007/978-3-540-77200-2_10, MR 2432534). En particulier Théorème 3, p. 193.
  5. ↑ John H. Reif, « Depth-first search is inherently sequential », Information Processing Letters, vol. 20, no 5,‎ , p. 229–234 (DOI 10.1016/0020-0190(85)90024-9, MR 801987).
  6. ↑ Alok Aggarwal et Richard J. Anderson, « A random NC algorithm for depth first search », Combinatorica, vol. 8, no 1,‎ , p. 1–12 (DOI 10.1007/BF02122548, MR 951989).
  7. ↑ David R. Karger et Rajeev Motwani, « An NC algorithm for minimum cuts », SIAM Journal on Computing, vol. 26, no 1,‎ , p. 255–272 (DOI 10.1137/S0097539794273083, MR 1431256).
  8. ↑ Bruno Courcelle, « On the expression of graph properties in some fragments of monadic second-order logic », dans Neil Immerman et Phokion G. Kolaitis, Proc. Descr. Complex. Finite Models, Amer. Math. Soc., coll. « DIMACS » (no 31), (MR 1451381, lire en ligne), p. 33–62.
  9. ↑ Gary Chartrand et Hudson V. Kronk, « Randomly traceable graphs », SIAM Journal on Applied Mathematics, vol. 16, no 4,‎ , p. 696–700 (DOI 10.1137/0116056, MR 0234852).
  10. ↑ Jaroslav Nešetřil et Patrice Ossona de Mendez, « Bounded height trees and tree-depth », dans Sparsity: Graphs, Structures, and Algorithms, Heidelberg, Springer, coll. « Algorithms and Combinatorics » (no 28), (ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4, MR 2920058), p. 115–144.
  11. ↑ Hubert de Fraysseix et Pierre Rosenstiehl, « A depth-first-search characterization of planarity », Graph theory (Cambridge, 1981), Amsterdam, North-Holland, vol. 13,‎ , p. 75–80 (MR 671906)
  12. ↑ Hubert de Fraysseix, Patrice Ossona de Mendez et Pierre Rosenstiehl, « Trémaux trees and planarity », International Journal of Foundations of Computer Science, vol. 17, no 5,‎ , p. 1017–1029 (DOI 10.1142/S0129054106004248, MR 2270949, arXiv math/0610935).
  13. ↑ Reinhard Diestel et Imre Leader, « Normal spanning trees, Aronszajn trees and excluded minors », Journal of the London Mathematical Society, vol. 63, no 1,‎ , p. 16–32 (DOI 10.1112/S0024610700001708, MR 1801714, lire en ligne).
  14. ↑ Nathan Bowler, Stefan Geschke et Max Pitz, « Minimal obstructions for normal spanning trees », Fund. Math., vol. 241, no 3,‎ , p. 245-263 (MR 3778904, arXiv 1609.01042).
  15. ↑ Reinhard Diestel, « End spaces and spanning trees », Journal of Combinatorial Theory Series B, vol. 96, no 6,‎ , p. 846–854 (DOI 10.1016/j.jctb.2006.02.010, MR 2274079).

Articles liés[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Arbre_de_Trémaux&oldid=208806985 ».