Bout (théorie des graphes)

Les bouts de graphes ont été définis par Rudolf Halin en 1964[1] en termes de classes d'équivalence de chemins infinis[2]. Un rayon dans un graphe infini est une chaîne simple infinie, c'est-à-dire une suite infinie v₀, v₁, v₂, ... de sommets tous distincts et telle que deux sommets consécutifs sont les extrémités d'une arête. D'après la définition de Halin, deux rayons r₀ et r₁ sont équivalents s'il existe un troisième rayon r₂ (pas nécessairement distinct des deux premiers) qui contient une infinité de sommets de chacun des rayons r₀ et r₁. Cette relation est une relation d'équivalence : la réflexivité et la symétrie sont claires, la transitivité aussi se démontre. Un bout est défini par Halin comme une classe d'équivalence de cette relation.

Une autre définition de cette relation d'équivalence fait appel à la notion de queue d'un rayon : une queue d'un rayon v₀, v₁, v₂, … est toute suite v_n, v_n+1, ... formée des sommets du rayon à partir du n-ième élément. la définition est la suivante : deux rayons r₀ et r₁ sont équivalents si, pour tout ensemble fini S de sommets du graphe G, r₀ et r₁ ont une queue contenue dans la même composante connexe du graphe G \S . Ceci est bien une relation d'équivalence puisque, comme S est fini, il n'existe qu'une seule composante connexe du graphe G \S pour chaque rayon[3].

Les bouts ont aussi une caractérisation plus concrète en termes de refuges (en), qui sont des fonctions qui décrivent des stratégies d'évasion dans des jeux de type poursuite-évasion (en) dans un graphe G[4]. Dans le jeu en question, un voleur tente d'échapper à une équipe de policiers en se déplaçant de sommet en sommet le long des arêtes du graphe G. La police dispose d'un hélicoptère et n'a donc pas besoin de suivre les arêtes. Le voleur peut voir l'arrivée de la police et peut choisir l'arête suivante avant que l'hélicoptère n’atterrisse. A refuge est une fonction β qui envoie tout ensemble X de positions de la police sur une des composantes connexes du sous-graphe obtenu en supprimant les sommets de X; un voleur peut échapper à la police en se déplaçant, à chaque tour, à l'intérieur d'une de ces composantes. Les refuges doivent satisfaire à une propriété de consistance (le voleur ne peut pas se déplacer par des sommets sur lesquels la police a déjà atterri) : si X est un sous-ensemble de Y, et si X et Y sont tous deux des ensembles de positions valides pour la police, alors β(X) doit être un sur-ensemble de β(Y). Un refuge a ordre k si la collection des positions de la police pour lesquelles il fournit une stratégie d'évasion comprend tous les ensembles de moins de k sommets du graphe; en particulier, il a ordre ℵ₀ s'il envoie toute ensemble fini X de sommets sur une composante de G \ X. Tout rayon de G correspond à un refuge d'ordre ℵ₀, à savoir à la fonction β qui associe à un ensemble fini X l'unique composante de G \ X qui contient une infinité de sommets du rayon. Réciproquement, tout refuge d'ordre ℵ₀ peut être défini de cette manière[5]. Deux rayons sont équivalents si et seulement s'ils définissent le même refuge ; ainsi il y a bijection entre les notions de bouts d'un graphe et de refuge d'ordre ℵ₀.

• Un graphe G qui est lui-même un rayon possède une infinité de rayons, chacun commençant en un sommets de G. Tous ces rayons sont équivalents, et G n'a qu'un seul bout.

• Un graphe G qui est un graphe grille infini possède une infinité de rayons dont les sommets sont disjoints. Il n'a pourtant qu'un seul bout. Cela se voit en constatant qu'après la suppression d'un ensemble quelconque mais fini de sommets, le graphe restant a exactement une composante connexe infinie.

• Quand G est un graphe sans cycle, l'intersection de deux rayons est soit une chaîne soit un rayon ; deux rayons sont équivalents si leur intersection est un rayon. Si un sommet racine est choisi dans chaque composante connexe de G, alors chaque bout de G contient un rayon unique dont l'origine est la racine de sorte que les bouts sont en bijection avec ces rayons canoniques. Tout graphe dénombrable G a un arbre couvrant qui a le même ensemble de bouts que G[6]. Toutefois, il existe des graphes infinis de cardinalité non dénombrable avec un seul bout et dans lequel chaque arbre couvrant a une infinité de bouts[7] - [8] - [9].

En topologie, il existe une notion de bout plus ancienne et similaire à celle de bout en théorie des graphes ; notion qui date de Freudenthal 1931. Si un espace topologie peut être couvert par suite emboîté d'ensembles compacts ${\displaystyle \kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots }$, alors un bout de l'espace est la suite ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$ des complémentaires de ces ensembles compacts. Cette définition ne dépend pas du choix des ensembles compacts : les bouts définis par un choix peuvent être mis en correspondance bijective avec les bouts définis par un autre choix.

Un graphe infini G peut être muni d'une structure d'espace topologique de deux manières différentes mais voisines :

• On remplace chaque sommet du graphe par un point et chaque arête par un intervalle unité ouvert ; on obtient un espace séparé à partir du graphe, en déclarant qu'un ensemble S est ouvert quand l'intersection de S avec une arête du graphe est un sous-ensemble ouvert de l'intervalle unité.
• On remplace chaque sommet par un point et chaque arête par un point ; on obtient un espace non séparé dans lequel les ensembles ouverts sont les ensembles S qui ont la propriété que si un sommet v of G est dans S, il en est de même pour toute arête dont v est une extrémité.

Dans les deux cas, un sous-graphe fini de G correspond à un sous-espace compact de l’espace topologique, et tout sous-espace compact correspond à un sous-graphe fini possédant dans le premier cas un nombre fini de sous-ensembles stricts d'arêtes. Ainsi, un graphe peut être couvert par une suite emboîtée d'ensembles compacts si et seulement s'il est localement fini, c'est-à-dire s'il a un nombre fini d'arêtes incidentes à chaque sommet.

Si un graphe G est connexe et localement fini, il possède une couverture compacte dans laquelle l'ensemble κ_i est l'ensemble des sommets à distance au plus i d'un sommet initial arbitraire. Dans ce cas tout refuge β définit un bout de l'espace topologique dans lequel ${\displaystyle U_{i}=\beta (\kappa _{i})}$. Réciproquement, si ${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$ est un bout de l'espace topologique défini à partir de G, il définit un refuge dans lequel β(X) est la composante contenant U_i, où i est un nombre assez grand pour que κ_i contienne X. Ainsi, pour des graphes connexes et localement finis, les bouts topologiques sont en bijection avec les bouts en théorie des graphes[10].

Pour les graphes qui ne sont pas localement finis, il est toujours possible de définir un espace topologique à partir du graphe et ses bouts. Cet espace peut être représenté comme espace métrique si et seulement si le graphe possède un arbre de Trémaux (ou arbre couvrant normal), c'est-à-dire un arbre couvrant enraciné tel que toute arête a ses extrémités sur une chaîne de l'arbre partant de la racine. Si un arbre couvrant normal existe, il a le même ensemble de bouts que le graphe : tout bout du graphe contient exactement une chaîne infinie de l'arbre[11].