Sept ponts, une seule promenade ?

Un réseau informatique, un plan de transports, des interactions biologiques ou des liens entre personnes ont un point commun : on peut parfois oublier presque toute leur apparence et ne garder que les objets et les relations qui les relient. Les graphes sont faits pour cela. Selon les problèmes, leurs liaisons peuvent être orientées, pondérées ou multiples ; ici, nous allons commencer par le cadre le plus simple, puis l'élargir juste assez pour revenir à une énigme célèbre du XVIIIe siècle.

Avant de commencer

Vous pouvez vous lancer si... vous savez lire un dessin, compter et raisonner sur quelques situations simples.

Nous remettrons en place... les nombres pairs et impairs, puis une façon très utile de compter la même chose de deux manières.

Vous allez explorer... le passage d'une situation concrète à un modèle, la formulation de conjectures et la démonstration d'une impossibilité.

Le problème des sept ponts

Au XVIIIe siècle, la ville prussienne de Königsberg était traversée par la Pregel. Quatre zones de terre étaient reliées par sept ponts. Une question très simple circulait :

Peut-on effectuer une promenade qui traverse chacun des sept ponts exactement une fois ?

Il n'est pas demandé de revenir au point de départ. Prenez si possible un crayon et une feuille et essayez plusieurs promenades. Vous pouvez changer le lieu de départ, le premier pont choisi, puis l'ordre des suivants. Si tous vos essais échouent, cela prouve-t-il pour autant que la promenade est impossible ?

Une carte ancienne de Königsberg, avec les sept ponts mis en évidence.

Le fil du parcours. Pour décider sans tester toutes les promenades, il va falloir oublier une partie de la géographie et ne garder que ce qui compte pour passer d'un lieu à un autre. C'est exactement le rôle des graphes.

I — Deux dessins, un même graphe

1. Les deux dessins suivants ont des formes très différentes.

Deux dessins d'un même réseau.

(a) Dans chacun des deux dessins, relever les lettres directement reliées à A, puis à B, C, D et E. Les deux dessins décrivent-ils le même réseau ? Justifier sans mesurer aucune longueur ni aucun angle.

Définition — un graphe

Un graphe permet de représenter des objets et les relations qui les relient. Les objets sont représentés par des sommets ; une relation entre deux objets est représentée par une arête reliant les deux sommets correspondants. La position des sommets, la longueur ou la forme des arêtes ne font pas partie du graphe : seules les connexions comptent. Deux sommets reliés par une arête sont appelés voisins.

(b) Combien le graphe précédent possède-t-il de sommets ? d'arêtes ? Donner les voisins de B puis ceux de E.

Le degré d'un sommet est le nombre d'arêtes qui ont ce sommet pour extrémité.

(c) Déterminer le degré de chacun des cinq sommets. Vérifier que les deux dessins donnent les mêmes résultats. Que confirme cette vérification ?

Attention

Lorsqu'une arête en croise une autre sur le dessin, le point de croisement n'est pas un nouveau sommet, sauf si un sommet y est explicitement marqué.

IDÉEUn graphe ne cherche pas à reproduire fidèlement un dessin : il conserve seulement les objets et les liaisons qui nous intéressent.

II — Compter deux fois

2. Six personnes se rencontrent. Un trait entre deux personnes signifie qu'elles se sont serré la main exactement une fois.

Le graphe des poignées de main.

(a) Combien de poignées de main ont eu lieu ? Calculer aussi le degré de chacun des six sommets, puis additionner les six degrés.

(b) Pourquoi la somme obtenue compte-t-elle chaque poignée de main exactement deux fois ? Expliquer pourquoi le même raisonnement vaut pour n'importe quel graphe fini et compléter :

$$\boxed{\text{somme des degrés}=2\times\text{nombre d'arêtes}}$$

(c) Nous allons en tirer une conséquence sur les degrés impairs. Avancer étape par étape :

• La somme de tous les degrés est-elle paire ou impaire ?
• Si l'on additionne seulement les degrés pairs, la somme obtenue est-elle paire ou impaire ?
• Que peut-on alors dire de la somme des degrés impairs ?
• Une somme d'un nombre impair de nombres impairs peut-elle être paire ?

En déduire que, dans tout graphe fini, le nombre de sommets de degré impair est pair.

Pourquoi ce raisonnement est utile

Nous n'avons pas vérifié une multitude de dessins : nous avons trouvé une raison valable pour tous les graphes finis. Chaque arête possède exactement deux extrémités.

IDÉEUne propriété très simple — chaque arête touche deux sommets — impose déjà une contrainte globale à tout le graphe.

III — Traverser chaque arête une seule fois

3. Pour chacun des trois graphes ci-dessous, essayez de tracer d'un seul geste un parcours utilisant chaque arête exactement une fois, sans lever le crayon. On peut repasser par un sommet, mais jamais par une arête déjà utilisée.

Trois graphes à parcourir.

(a) Pour chaque graphe, dire si vous avez trouvé un tel parcours. Lorsqu'il existe, noter son sommet de départ et son sommet d'arrivée. Calculer ensuite les degrés de tous les sommets.

Vocabulaire

Un parcours utilisant chaque arête exactement une fois est appelé ici une chaîne eulérienne. S'il revient à son sommet de départ, on parle de circuit eulérien.

(b) À partir des trois exemples, quelle règle soupçonnez-vous entre les sommets de degré impair et les extrémités d'une chaîne eulérienne ?

(c) Considérons maintenant une chaîne eulérienne quelconque. Chaque fois qu'un sommet est traversé en cours de route, une arête sert à y arriver et une autre à en repartir : ces arêtes se groupent donc par paires. Expliquer pourquoi cela entraîne les deux affirmations suivantes :

• si le parcours revient à son point de départ, tous les sommets ont un degré pair ;
• s'il part d'un sommet et se termine à un autre, seuls le départ et l'arrivée peuvent avoir un degré impair.

Ce que nous savons désormais

Si un parcours utilise chaque arête exactement une fois, alors les degrés doivent respecter les règles précédentes. C'est tout ce dont nous aurons besoin pour répondre au problème des ponts.

IV — Retour à Königsberg

4. Revenons maintenant au problème des ponts. Pour raisonner, on va remplacer chaque zone de terre par un sommet et chaque pont par une arête. Il arrive que deux mêmes zones soient reliées par plusieurs ponts : dans le graphe, on dessinera alors plusieurs arêtes entre les mêmes sommets. Chaque arête est comptée séparément dans le degré.

Schéma simplifié : les quatre zones de terre et les sept ponts sont conservés, pas les distances ni les formes exactes.

(a) Attribuer les lettres A, B, C et D aux quatre zones de terre, puis construire le graphe correspondant : un sommet pour chaque zone et une arête pour chacun des sept ponts. Les arêtes peuvent être courbes : seules leurs extrémités comptent.

(b) Le raisonnement de la question 3(c) change-t-il lorsque deux mêmes sommets sont reliés par plusieurs arêtes ? Expliquer en une phrase.

(c) Calculer le degré de chacun des quatre sommets de votre graphe. Combien de sommets ont un degré impair ?

(d) En utilisant la règle démontrée à la question 3(c), montrer qu'aucune promenade ne peut traverser chacun des sept ponts exactement une fois. Votre raisonnement doit couvrir tous les choix possibles de départ et d'arrivée.

(e) Quelles informations de la carte ont disparu dans le graphe ? Quelle information essentielle a été conservée ? Pourquoi quelques essais infructueux sur une carte ne prouvaient-ils pas l'impossibilité, alors que le raisonnement précédent la prouve ?

Un mot d'histoire. Euler présente sa solution en 1735 ; son article paraît en 1741. La solution détaillée montrera également le dessin utilisé par Euler lui-même.

Pour prolonger. Lorsque les degrés ne créent aucun obstacle, l'existence et la construction d'un tel parcours restent une autre question, qui pourra faire l'objet d'un prochain parcours.

Crédits des illustrations

• Bogdan Giuşcă — Wikimedia Commons — adaptation d'une carte du domaine public ; affichage redimensionné par AlgèBrille — Source · Licence CC BY-SA 3.0
• Chris-martin — Wikimedia Commons — version PNG du diagramme, redimensionnée à l'affichage par AlgèBrille — Source · Licence CC BY-SA 3.0