Bout (théorie des graphes)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/4/41/Typy_kultury_organizacyjnej%2C_Ateny_II_%28ubt%29.svg/220px-Typy_kultury_organizacyjnej%2C_Ateny_II_%28ubt%29.svg.png)
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 fournit une décomposition pour les groupes ayant plus d'un bout.
Définition et caractérisation
[modifier | modifier le code]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 v0, v1, v2, ... 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 r0 et r1 sont équivalents s'il existe un troisième rayon r2 (pas nécessairement distinct des deux premiers) qui contient une infinité de sommets de chacun des rayons r0 et r1. 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 v0, v1, v2, … est toute suite vn, vn+1, ... formée des sommets du rayon à partir du n-ième élément. la définition est la suivante : deux rayons r0 et r1 sont équivalents si, pour tout ensemble fini S de sommets du graphe G, r0 et r1 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. Un 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 ℵ0 s'il envoie toute ensemble fini X de sommets sur une composante de G \ X. Tout rayon de G correspond à un refuge d'ordre ℵ0, à 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 ℵ0 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 ℵ0.
Exemples
[modifier | modifier le code]- 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].
Relation avec les bouts en topologie
[modifier | modifier le code]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 , alors un bout de l'espace est une suite de composantes connexes 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 . Réciproquement, si est un bout de l'espace topologique défini à partir de G, il définit un refuge dans lequel β(X) est la composante contenant Ui, 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].
Bouts particuliers
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/5/53/Tiling_Regular_6-3_Hexagonal.svg/220px-Tiling_Regular_6-3_Hexagonal.svg.png)
Bout libre
[modifier | modifier le code]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 une 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
[modifier | modifier le code]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[12],[13].
Graphes particuliers
[modifier | modifier le code]Graphes symétriques et presque symétriques
[modifier | modifier le code]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 Cheeger
- ,
où V parcourt les ensembles finis non vides de sommets du graphe et où 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
[modifier | modifier le code]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Cayley_graph_of_F2.svg/220px-Cayley_graph_of_F2.svg.png)
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
[modifier | modifier le code]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 fournit une classification des groupes qui ont plus d'un bout[14],[15]. On a plus précisément :
- Un groupe infini finiment engendré possède deux bouts si et seulement s'il a un sous-groupe cyclique d'indice fini .
- 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 finie.
- Tous les autres groupes infinis finiment engendrés ont exactement un bout.
Notes et références
[modifier | modifier le code]Notes
[modifier | modifier le code]- Halin (1964).
- Toutefois, comme l'observent Krön et Möller 2008, les bouts de graphes ont déjà été considérés en 1945 (Freudenthal 1945).
- C'est la formulation utilisée dans Diestel 2017, p. 217.
- Le terme de « refuge », et le fait que deux rayons définissent le même refuge si et seulement s'ils sont équivalents son dus à Robertson, Seymour et Thomas 1991. Diestel et Kühn 2003 démontrent que chaque refuge provient d'un bout, ce qui établit la bijection avec les bouts, tout en utilisant une terminologie différente où les refuges sont appelées « directions ».
- La preuve de Diestel et Kühn 2003 que tout refuge peut être défini par un rayon n'est pas facile.
- Dans la formulation originale de Halin 1964, où les bouts sont définis comme des classes d'équivalence de rayons, chaque classe d'équivalence de rayons de G contient une classe d'équivalence non vide unique de rayons de l'arbre couvrant. En termes de refuges, il y a une correspondance bijective entre les refuges d'ordre ℵ0 de G et de ses arbres couvrants T pour laquelle pour tout ensemble X et toute paire correspondante de refuges βT et βG.
- Seymour et Thomas (1991).
- Thomassen (1992).
- Diestel (1992).
- Diestel et Kühn (2003).
- Diestel (2006).
- Halin (1965).
- Diestel (2004).
- Stallings (1968).
- Stallings (1971).
Bibliographie
[modifier | modifier le code]- Reinhard Diestel, Graph Theory, Springer-Verlag, coll. « Graduate Texts in Mathematics » (no 173), , 5e é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, nos 1–3, , 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, , p. 237–242 (DOI 10.1007/BF02941538, MR 2112834).
- 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).
- Reinhard Diestel et Daniela Kühn, « Graph-theoretical versus topological ends of graphs », Journal of Combinatorial Theory, series B, vol. 87, no 1, , 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, , p. 692–713 (DOI 10.1007/BF01174375).
- Hans Freudenthal, « Über die Enden diskreter Räume und Gruppen », Commentarii Mathematici Helvetici, vol. 17, , p. 1–38 (DOI 10.1007/bf02566233, MR 0012214).
- Rudolf Halin, « Über unendliche Wege in Graphen », Mathematische Annalen, vol. 157, no 2, , 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, nos 1–2, , 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, no 1, , 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, nos 1–3, , 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, nos 1–3, , 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, no 4, , 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 2e série, vol. 88, no 2, , 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 » (no 4), (MR 0415622).
- Carsten Thomassen, « Infinite connected graphs with no end-preserving spanning trees », Journal of Combinatorial Theory, series B, vol. 54, no 2, , p. 322–324 (DOI 10.1016/0095-8956(92)90059-7, MR 1152455, hdl 10338.dmlcz/127625
).