Bout (théorie des graphes)

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. Les bouts de graphes ont été définis par Rudolf 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 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.