Compte rendu de l’Association française pour l’Avancement des Sciences, 15eme session (1886), pt. 2, 49–53 + Plates I & II.
In his paper on the Königsberg bridges, Euler stated that if a finite connected graph has an even number of edges at each vertex then it is possible to walk round the graph in such a way that every edge is traversed once and once only. In the paper below, Tarry shows how to calculate the number of ways in which this can be done.
As Euler showed, every such walk returns to its starting point. Tarry’s convention for counting the walks is that reversing the direction of a walk creates a different one, but changing the starting point does not.
{49}
J’appelle labyrinthe rentrant un labyrinthe tel qu’à chaque point de son parcours aboutisse toujours un nombre pair d’allées.
Les points du parcours auxquels aboutissent plus de deux allées seront les carrefours du labyrinthe.
Je désignerai spécialement sous le nom d’impasse toute allée dont les extrémités aboutissent à un même carrefour.
{50}
Si dans un labyrinthe rentrant on supprime une impasse, le nombre de parcours distincts du labyrinthe ainsi réduit, multiplié par le nombre de ses allées qui aboutissent au carrefour situé sur l’impasse supprimée, est égal au nombre de parcours distincts du labyrinthe primitif. On aura bien soin de compter pour deux allées chacune des autres impasses qui pourraient être annexées à ce carrefour.
Désignons par N le nombre de parcours distincts du labyrinthe réduit et par 2n le nombre de ses allées aboutissant au carrefour situé sur l’impasse supprimée.
Je dis que le nombre de parcours distincts du labyrinthe primitif est égal à N×2n [14].
En effet, considérons l’un quelconque des N parcours distincts du labyrinthe réduit.
Dans ce parcours on passera n fois par le carrefour de l’impasse supprimée, et à l’un quelconque de ces n passages l’on peut interrompre le parcours en arrivant au carrefour de l’impasse, parcourir entièrement cette impasse, ce qui peut se faire dans deux sens différents, et, revenu au carrefour, achever le parcours commencé.
Il résulte de là que chacun des N parcours distincts du labyrinthe réduit fournira 2n parcours distincts du labyrinthe primitif.
Les N parcours distincts du labyrinthe réduit fourniront ainsi N×2n parcours du labyrinthe primitif.
Il est évident que ces N×n parcours du labyrinthe primitif sont tous distincts, et qu’il n’existe pas d’autres manières de parcourir en une seule course le labyrinthe primitif.
Le théorème est donc démontré.
Si à un carrefour aboutissent 2(n+k) allées, dont 2k appartiennent à k impasses, le nombre de parcours distincts du labyrinthe proposé est égal au produit de n(n+1)(n+2).....(n+k−1)2k par le nombre de parcours distincts du labyrinthe réduit obtenu par la suppression des k impasses du labyrinthe proposé.
En effet, ajouter successivement chacune de ces k impasses au labyrinthe réduit revient à multiplier successivement les nombres de parcours distincts par 2n, 2(n+1), 2(n+2),....2(n+k−1)
On voit que le théorème des impasses permet d’éliminer les impasses du labyrinthe proposé et de ramener le calcul du nombre de parcours distincts au cas où le labyrinthe ne possède plus d’impasses.
{51}
Étant donné un labyrinthe rentrant sans impasses et comprenant k carrefours, si l’on désigne par 2n le nombre d’allées aboutissant à l’un de ses carrefours, N, le nombre de parcours distincts du labyrinthe proposé est égal à la somme des nombres de parcours distincts de 1×3×5×7..... (2n−1) labyrinthes rentrants ne comprenant plus que (k−1) carrefours.
Ces 1×3×5×7..... (2n−1) labyrinthes nouveaux s’obtiennent en groupant en n couples de deux allées, de toutes les manières possibles, les 2n allées aboutissant au carrefour N, et en remplaçant ensuite, dans chacun de ces groupements, chaque couple de deux allées par une allée nouvelle joignant les deux carrefours où aboutissent les extrémités de ce couple d’allées ou, dans le cas particulier où les deux allées du couple aboutissent à un même carrefour, par une impasse passant par ce carrefour.
Groupons les 2n allées du carrefour N par couples de deux allées, de toutes les manières possibles.
Nous obtiendrons ainsi (2n−1)(2n−3).....5×3×1 groupements différents.
A chacun de ces groupements faisons correspondre tous les parcours du labyrinthe proposé dans lesquels, à chaque passage par le carrefour N, l’allée qui y conduit et l’allée qui en éloigne appartiennent à un couple du groupement considéré.
Il est aisé de voir que le nombre de parcours cherché sera égal à la somme des nombres de parcours distincts correspondant à chaque groupement, de la manière qui vient d’être indiquée.
Ceci admis, considérons les parcours de l’un de ces groupements, et examinons les n couples de deux allées qui le composent.
Dans chacun de ces n couples, les deux allées, considérées comme issues du carrefour N, aboutissent soit à deux carrefours différents A, B, soit à un même carrefour C.
Dans le premier cas, nous pouvons évidemment remplacer les deux allées NA, NB, par une allée nouvelle AB, reliant les carrefours A et B, sans changer le nombre de parcours, car cela revient à remplacer les trajets ANB ou BNA par les trajets équivalents AB ou BA.
Dans le second cas, on voit aussi clairement que les deux allées reliant les carrefours N et C peuvent être remplacées par une impasse passant par le carrefour C.
Le théorème est donc démontré complètement.
En appliquant aux nouveaux labyrinthes la même méthode d’élimination d’impasses et de réduction du nombre de carrefours, nous arri-{52}vons forcément, par réductions successives, à n’avoir plus a considérer que des labyrinthes sans impasses ne comprenant plus que deux carrefours, et le problème pourra être résolu.
On démontre, en effet, avec la plus grande facilité, que le nombre de parcours distincts d’un labyrinthe ne comprenant que deux carrefours reliés par 2n allées est égal à 2(2n−1)(2n−2).....4×3×2×1, en tenant compte du sens du parcours.
Remarque. — Un labyrinthe qui n’a que deux points impairs peut aussi être parcouru entièrement en une seule course et en ne passant qu’une fois par chaque allée.
On voit aisément que le nombre de parcours distincts de ce labyrinthe est le même que celui du labyrinthe rentrant que l’on obtiendrait en ajoutant une allée nouvelle reliant les deux points impairs.
Voir aux planches I et II, l’application de la méthode au calcul du nombre de parcours distincts du labyrinthe rentrant, dont les allées forment les côtés et les diagonales d’un heptagone.
Les cercles représentent les carrefours du labyrinthe.
Les lignes droites qui relient deux cercles représentent les allées du labyrinthe qui relient deux carrefours.
Les impasses, allées dont les extrémités aboutissent à un même carrefour, sont figurées par un triangle équilatéral ayant un sommet sur le cercle correspondant à ce carrefour.
La lettre indicatrice de chaque figure sert à représenter dans le calcul le nombre de parcours correspondant à cette figure, suppression faite des triangles ou impasses qu’elle peut comprendre.
Toutes les figures qui ont la même forme, ainsi réduite, sont désignées naturellement par la même lettre.
Le nombre isolé placé à côté de la figure indique combien de fois le nombre de parcours de la figure complète doit être compté.
A côté de chaque figure se trouve le calcul du nombre qui doit multiplier le nombre de parcours de la figure réduite, en vertu du théorème des impasses.
Les lettres indicatrices des figures représentant le nombre de parcours correspondant à cette figure réduite, on a le tableau suivant:
| X | = | 15H | T1 | = | 6D1 + 144D2 | |
| H | = | 8P1 + 4P2 + 8P3 + 4P4 | T2 | = | 2D1 + 16D2 | |
| T3 | = | 12D2 | ||||
| P1 | = | 6Q1 + 4Q2 + 16Q3 + 16Q4 | T4 | = | 2D2 + 4D3 | |
| P2 | = | 8Q1 + 16Q3 + 2Q5 + 16Q6 | T5 | = | D1 | |
| P3 | = | 2Q1 + Q2 | ||||
| P4 | = | 2Q1 + Q5 | D1 | = | 240 | |
| D2 | = | 12 | ||||
| Q1 | = | 6T1 + 24T2 + 48T3 | D3 | = | 2 | |
| Q2 | = | 8T1 + 24T2 + 64T4 | ||||
| Q3 | = | 2T1 + 4T2 | ||||
| Q4 | = | 2T2 + 4T3 | ||||
| Q5 | = | 48T2 + 24T5 | ||||
| Q6 | = | 2T2 + 2T5 |
{53} En effectuant les calculs indiqués par ce tableau, on trouve que le nombre de parcours cherché X est égal à 129,976,320 [15].
Remarque importante. – Deux figures ont le même nombre de parcours lorsqu’on peut les faire correspondre, carrefour à carrefour, de telle sorte que le nombre d’allées qui relient deux carrefours quelconques dans l’une de ces figures soit égal au nombre d’allées qui relient les deux carrefours correspondants dans l’autre figure.
L’application de ce théorème, presque intuitif, abrège considérablement le travail en permettant de donner une représentation uniforme à des figures qui paraissent d’aspects différents.
Ainsi tous les hexagones peuvent être représentés par la même figure H.