SUR LA THÉORIE DES ARBRES GÉOMÉTRIQUES

Nous avons vu que, dans l'application de la seconde règle, on doit rétrograder quand on arrive, par une voie nouvelle, à un carrefour exploré. Supposons que Ton supprime, dans le réseau, un petit fragment du chemin qui aboutit à ce carrefour, et que Ton fasse la même opération à tous les endroits de recul ; le réseau se transforme alors dans une autre figure géométrique que Ton désigne indistinctement sous le nom d'arbre, de ratwificatiùn, à! arborescence; les chemins prennent le nom de branches ou de rameaux, et les carrefours le nom d'embranchements ou de noeuds. De pareilles configurations ont été étudiées par MM. Jordan, Sylvester, Cayley, Septimus Tebay, et tout récemment par M. le prince C. de Polignac (').

On donne habituellement de l'arbre géométrique la définition

(«) Jordan, Journal de Borchardt. — Sylvestbr, Educational Times. — Caylsy, British Association Report, 1875. — De Polignac, Bulletin de la Société mathimatiquér t. VIII, p. 1-20.

52 Troisième récréation.

suivante : De chaque nœud on peut, en suivant les branches, parvenir à un nœud quelconque, mais par un seul chemin. Cette théorie a été considérablement simplifiée par M. de Polignac au moyen d'une remarque fondamentale. En effet, toute ramification peut être tracée au moyen d'un certain nombre de traits continus, sans répétition ni arrêt, c'est-à-dire en partant de l'extrémité d'une branche et en continuant jusqu'à ce que Ton arrive à l'extrémité d'une autre branche ou à une branche déjà parcourue. Observons que le trait doit traverser une ligne quoique déjà tracée, s'il peut continuer au delà, sans cheminer le long de cette ligne. Cela posé :

Remarque fondamentale. — De quelque manière que l'on trace une ramification sans répétition ni arrêt, le nombre des parcours sera toujours le même.

En effet, faisons une coupure à toutes les branches joignant deux nœuds, on décomposera la ramification en une série d'étoiles. On recomposera la ramification en rendant aux étoiles leurs rayons communs. Pour chaque étoile, prise séparément, la propriété fondamentale est évidente. Désignons par Ni, Nj, N 8 , ..., N p , les nombres des traits relatifs à chaque étoile; par p le nombre des nœuds ou des étoiles. Si Ton réunit maintenant les deux premières étoiles, on perd un trait sur la somme des parcours relatifs à chaque étoile; réunissons la deuxième étoile à la troisième, nous perdons encore un trait; par suite, si l'on désigne par N le nombre des traits. qui ont servi. à tracer la ramification, on a

N == N t 4- N 2 4- N 3 4- ... 4- N p — (p - i ). Nous appellerons le nombre N la base de la ramification; on

Le jeu des labyrinthes. 53

peut exprimer les nombres N t , N s , . . . , et par suite le nombre N lui-même d'après Tordre des nœuds, ou étoiles, c'est-à-dire par le nombre de branches ou de rayons qui y aboutissent. Le noeud le plus simple est le noeud ternaire ou d'ordre 3 ; soit, en général, m q l'ordre d'un noeud on a d'abord m au moins égal à trois ; le nombre N 9 des traits qui permettent deNiessinerce nœud est égal à la moitié de m q , si m q est pair, etàla moitié de m^4- i , lorsque m q est impair; c'est donc, dans tous les cas, le plus grand nombre

entier contenu dans la fraction — 2

Ce nombre est habituellement représenté par le symbole par conséquent la formule précédente peut s'écrire

On détermine ainsi la base de la ramification connaissant le nombre et l'ordre des nœuds.

Désignons par / le nombre des extrémités libres des branches, et supposons que la ramification n'ait que des nœuds d'ordre ternaire ; on a alors, quel que soit le nombre des nœuds ternaires, la formule

Cette formule est évidente pour une étoile à trois rayons; si l'on ajoute un nœud ternaire à l'extrémité libre d'une branche, on remplace celle-ci par deux autres, et Ton ajoute un trait ; lorsque l'on forme un nœud ternaire par l'addition d'un rameau sur une branche, on ajoute un trait et une extrémité libre. Dans les deux

54 Troisième récréation.

cas, les deux membres de la formule précédente augmentent d'une unité. Donc cette formule est générale.

Désignons en général par j?* le nombre des nœuds d'ordre k ; on a, pour deux nœuds séparés d'ordre quaternaire {p\ et p\ étant l'unité),

En réunissant deux nœuds quaternaires par une extrémité commune, le nombre total des traits diminue d'une unité, mais deux extrémités disparaissent;, on a donc

N -H I = N' H- N% /'-*-/' = / -*- 2, p\+fk = Pk\

par suite, on a pourla ramification des deux nœuds quaternaires

N = /-i-jv,

cette formule s'applique à une ramification formée d'un nombre quelconque de nœuds quaternaires. On démontrera de même que la base d'une ramification ne contenant que des nœuds de cinquième ordre en nombre p^ est donnée par la formule

Plus généralement, lorsqu'une ramification ne contient que des nœuds d'ordre 2 p, on a

et lorsqu'elle ne contient que des nœuds d'ordre ap-t- i 9 on a encore

Le jeu des labyrinthes. 55

Par suite, en réunissant deux ou plusieurs ramifications par deux extrémités libres, on obtient la formule générale N=l-i-(p.+p t ) -% ip,+p,) - 3(ft+ft) — 4(J*m+J*u)---

Nous indiquerons dans la Note III placée à la fin du volume les divers rapprochements que l'on peut établir entre la théorie des arbres et le jeu des ponts et des lies.