SUR LA THEORIE DES ARBRES GEOMETRIQUES

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 l'on supprime, dans le réseau^ un petit fragment du chemin qui aboutit à ce carrefour, et que l'on 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 l'on désigne indistinctement sous le nom à' arbre, de ramification, d'arborescence; les chemins prennent le nom de branches ou de rameaux, et les carrefours le nom d'embranchements ou de nœuds. De pareilles configurations ont été étudiées par MM. Jordan, Sylvester, Gayley, Septimus Tebay, et tout récemment par M. le prince C. de Polignac (').

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

(^) Jordan, Journal de Borchardt. — Sylvester, Educational Times.— Cayley, British Association Report, iSyS. — De Polignac, Bulletin delà Société mathématique, t. VIII, p. 120.

Troisième récréatioyi.

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 l'on 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 Von 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, N2, N3, ..., N;,, les nombres des traits relatifs à chaque étoile ; par;? 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 = Ni -f- N2 -i- N3 -h ... -1- Np ~ (p - I ).

Nous appellerons le nombre N la base de la ramification; on

Le jeu des labyrinthes. 53

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

entier contenu dans la fraction '' "*

Ce nombre est habituellement représenté par le symbole

par conséquent la formule précédente peut s'écrire

. r ^n^ -- 1 1 ^ ^ ïmq-\- il

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

34 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 p^- le nombre des nœuds d'ordre k; on a, pour deux nœuds séparés d'ordre quaternaire {p\ Qt 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-hi = N'-i-N% /'-hr=r/4-2, p'.-i-p^^p,;

par suitCj on a pour la ramification des deux nœuds quaternaires

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 ^5 est donnée par la formule

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

N = / — I — (|x— r)i72ix;

et lorsqu'elle ne contient que des nœuds d'ordre 2{ji-h i, on a encore

N=r/— I — ((X— l)^2ix-f-i.

Le jeu des labyriyithes.

Par suite, en réunissant deux ou plusieurs ramifications par deux extrémités libres, on obtient la formule générale

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 îles.