Arbre de Trémaux
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. 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, un ingénieur français du qui a utilisé une sorte d'algorithme de parcours en profondeur comme stratégie pour résoudre des labyrinthes. Les arbres de Trémaux sont également été appelé arbres couvrants normaux, en particulier dans le contexte des graphes infinis. 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 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.