Bout (théorie des graphes)

Un graphe grille infini. les sommets sont les points d'intersection de droites. Le graphe a une infinité de rayons différents, mais il n'a qu'un seul bout.

En mathématiques, et dans la théorie des graphes infinis, un bout d'un graphe représente informellement une direction dans laquelle le graphe s'étend à l'infini. Les bouts se définissent, formellement, comme les classes d'équivalences de chaînes infinies ou, dans le cas de graphes localement finis, comme les bouts de certains espaces topologiques associés au graphe.

Les bouts de graphes peuvent être utilisés, via le graphe de Cayley, pour définir les bouts de groupes finiment engendrés. Les groupes finiment engendrés peuvent avoir un, deux, ou une infinité de bouts, et le théorème de Stallings sur les bouts de groupes fournit une décomposition pour les groupes ayant plus d'un bout.

Définition et caractérisation

Les bouts de graphes ont été définis par Rudolf HalinRudolf Halin en 1964 en termes de classes d'équivalence de chemins infinis. 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.

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. 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. 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 ℵ₀.

Exemples

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

Relation avec les bouts en topologie

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 $\kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots$, alors un bout de l'espace est la suite $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 sue 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 $U_{i}=\beta (\kappa _{i})$. Réciproquement, si $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.

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.

Bouts particuliers

Pavage hexagonal

Bout libre

Un bout E d'un graphe G est dit un bout libre s'il existe un ensemble fini X de sommets avec la propriété que X sépare E de tous les autres bouts du graphe (en termes de refuges, β_E(X) est disjoint de β_D(X) pour tout autre bout D). Halin 1964 prouve que si G a une infinité de bouts, ou bien il existe un bout qui n'est pas libre, ou bien il existe un famille infinie de rayons qui commence dans le même sommet et qui sont, à l'exception du sommet de départ, disjoints deux-à-deux.

Bout épais

Un bout épais d'un graphe G est un bout qui contient une infinité de rayons deux-à-deux disjoints. Le théorème de la grille de Halin (en) caractérise les graphes qui possèdent un bout épais : ce sont exactement les graphes qui possèdent un sous-graphe qui est une subdivision du pavage hexagonal.

Graphes particuliers

Graphes symétriques et presque symétriques

Mohar 1991 définit une graphe connexe localement fini comme étant « presque symétrique » s'il existe un sommet v et un entier D tel que, pour tout autre sommet w, il existe un automorphisme du graphe pour lequel l'image de v est à distance au plus D de w; de manière équivalente, un graphe connexe localement fini est presque symétrique si son groupe d'automorphismes a un nombre fini d'orbites. Mohar prouve que tout graphe connexe localement fini presque périodique possède soit deux, soit un nombre non dénombrable de bouts ; dans le dernier cas, les bouts ont une topologie d'un ensemble de Cantor. De plus, Mohar démontre que le nombre bouts contrôle la constante de Cheegerconstante de Cheeger

$h=\inf \left\{{|\partial V|}/{|V|}\right\}$,

où V parcourt les ensembles finis non vides de sommets du graphe et où $\partial V$ est l'ensemble des arêtes qui ont une extrémité dans V. Pour un graphe presque symétrique avec un nombre non dénombrable de bouts, on n h > 0; et pour un graphe presque symétrique avec seulement deux bout, h = 0.

Graphes de Cayley

Le grapphe de Cayley du groupe libre à deux générateurs a and b. Les bouts du groupe sont en bijection avec les rayons partant de l'élément neutre e jusqu'aux marges du dessin.

Pour tout groupe, un ensemble de générateurs du groupe définit un graphe de Cayley, dont les sommets sont les éléments du groupe et les arêtes les paires (x,gx) où g est un générateur. Dans le cas d'un groupe de type fini, les bouts du groupe sont définis comme les bouts de son graphe de Cayley ; la définition est indépendante du choix des générateurs au sens que pour deux ensembles de générateurs, il existe une bijection des bouts des graphes de Cayley correspondants.

Par exemple, tout groupe libre a un graphe de Cayley qui est un arbre. Le graphe de Cayley du groupe libre à un générateur est une chaîne infinie des deux côtés, avec deux bouts. Tout autre groupe libre a une infinité de bouts.

Théorème de Stallings sur les bouts de groupes

Tout groupe infini finiment engendré a 1, 2 ou une infinité de bouts, et le théorème de Stallings sur les bouts de groupes (en) fournit une classification des groupes qui ont plus d'un bout. On a plus précisément :

1. Un groupe infini finiment engendré possède deux bouts si et seulement s'il a un sous-groupe cyclique d'indice fini .
2. Un groupe infini finiment engendré possède une infinité de bouts si et seulement s'il est un produit libre amalgamé non trivial ou une extension HNN avec amalgamation fini.
3. Tous les autres groupes infinis finiment engendrés ont exactement un bout.

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « End (graph theory) » (voir la liste des auteurs).

Bibliographie

• Reinhard Diestel, Graph Theory, Springer-Verlag, coll. « Graduate Texts in Mathematics » (n^o 173), 2017, 5^e éd., 448 p. (ISBN 978-3-662-53622-3, lire en ligne).
• Reinhard Diestel, « The end structure of a graph: recent results and open problems », Discrete Mathematics, vol. 100, n^os 1–3,‎ 1992, p. 313–327 (DOI 10.1016/0012-365X(92)90650-5, MR 1172358).
• Reinhard Diestel, « A short proof of Halin's grid theorem », Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 74,‎ 2004, p. 237–242 (DOI 10.1007/BF02941538, MR 2112834).
• Reinhard Diestel, « End spaces and spanning trees », Journal of Combinatorial Theory, vol. 96, n^o 6,‎ 2006, p. 846–854 (DOI 10.1016/j.jctb.2006.02.010, MR 2274079).
• Reinhard Diestel et Daniela Kühn, « Graph-theoretical versus topological ends of graphs », Journal of Combinatorial Theory, vol. 87, n^o 1,‎ 2003, p. 197–206 (DOI 10.1016/S0095-8956(02)00034-5, MR 1967888).
• Hans Freudenthal, « Über die Enden topologischer Räume und Gruppen », Mathematische Zeitschrift, vol. 33,‎ 1931, p. 692–713 (DOI 10.1007/BF01174375).
• Hans Freudenthal, « Über die Enden diskreter Räume und Gruppen », Commentarii Mathematici Helvetici, vol. 17,‎ 1945, p. 1–38 (DOI 10.1007/bf02566233, MR 0012214).
• Rudolf Halin, « Über unendliche Wege in Graphen », Mathematische Annalen, vol. 157, n^o 2,‎ 1964, p. 125–137 (DOI 10.1007/bf01362670, MR 0170340, hdl 10338.dmlcz/102294).
• Rudolf Halin, « Über die Maximalzahl fremder unendlicher Wege in Graphen », Mathematische Nachrichten, vol. 30, n^os 1–2,‎ 1965, p. 63–85 (DOI 10.1002/mana.19650300106, MR 0190031).
• Bernhard Krön et Rögnvaldur G. Möller, « Metric ends, fibers and automorphisms of graphs », Mathematische Nachrichten, vol. 281, n^o 1,‎ 2008, p. 62–74 (DOI 10.1002/mana.200510587, MR 2376468, lire en ligne).
• Bojan Mohar, « Some relations between analytic and geometric properties of infinite graphs », Discrete Mathematics, vol. 95, n^os 1–3,‎ 1991, p. 193–219 (DOI 10.1016/0012-365X(91)90337-2, MR 1141939, lire en ligne).
• Neil Robertson, Paul Seymour et Robin Thomas, « Excluding infinite minors », Discrete Mathematics, vol. 95, n^os 1–3,‎ 1991, p. 303–319 (DOI 10.1016/0012-365X(91)90343-Z, MR 1141945).
• Paul Seymour et Robin Thomas, « An end-faithful spanning tree counterexample », Proceedings of the American Mathematical Society, vol. 113, n^o 4,‎ 1991, p. 1163–1171 (DOI 10.2307/2048796, JSTOR 2048796, MR 1045600).
• John R. Stallings, « On torsion-free groups with infinitely many ends », Annals of Mathematics 2^e série, vol. 88, n^o 2,‎ 1968, p. 312–334 (DOI 10.2307/1970577, JSTOR 1970577, MR 0228573).
• John R. Stallings, Group theory and three-dimensional manifolds : A James K. Whittemore Lecture in Mathematics given at Yale University, 1969, New Haven, Conn., Yale University Press, coll. « Yale Mathematical Monographs » (n^o 4), 1971 (MR 0415622).
• Carsten Thomassen, « Infinite connected graphs with no end-preserving spanning trees », Journal of Combinatorial Theory, vol. 54, n^o 2,‎ 1992, p. 322–324 (DOI 10.1016/0095-8956(92)90059-7, MR 1152455, hdl 10338.dmlcz/127625).