Arbre de Trémaux

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.

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] .

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 MSO₂, 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].

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].

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).

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].

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].