Glossaire

Select one of the keywords on the left…

Graphes et réseauxLes ponts de Königsberg

Reading time: ~20 min
Reveal all steps

Leonhard Euler est l'un des premiers mathématiciens à avoir réfléchi aux graphes et aux réseaux. Euler était intrigué par un vieux problème concernant la ville de Königsberg, près de la mer Baltique.

La rivière Pregel divise Königsberg en quatre parties distinctes, reliées par sept ponts. Est-il possible de se promener dans la ville en traversant tous les ponts exactement une fois - mais pas plus d'une fois? (Vous pouvez commencer et finir n'importe où, pas nécessairement au même endroit.)

Essayez de trouver un itinéraire valide en dessinant sur ces cartes:

Map 1

Map 2

Map 3

Map 4

Dans le cas de Königsberg, il semble impossible de trouver un itinéraire valable, mais certaines des autres villes fonctionnent. Euler a réussi à trouver une règle simple pouvant être appliquée à n’importe quelle ville, sans avoir à essayer beaucoup de possibilités - en utilisant la théorie des graphes.

Premièrement, nous devons convertir les cartes de la ville en graphes avec des arêtes et des sommets. Chaque île ou région terrestre est représentée par un sommetun bordune zone et chaque pont reliant deux régions est représenté par un bordsommetrue correspondant.

Le problème de "visiter une ville en traversant chaque pont exactement une fois" est devenu un problème de "dessiner un graphique en un trait continu tout en traçant chaque bord exactement une fois".

Sur papier, imaginez quelques graphes différents, puis essayez de déterminer lesquels peuvent être dessinés avec un seul trait continu.

Tout comme pour les cartes de villes précédentes, nous constatons que certains graphes sont possibles, d'autres non. Pour nous aider à comprendre pourquoi, étiquetons chaque sommet avec son degré:

Ces graphes sont possibles :

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

Ces graphes ne sont pas possibles :

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

En comparant ces nombres pour des graphes possibles et impossibles, il semble qu'un graphe puisse être tracé s'il n'a pas plus de deux sommets «impairs»n'a que des sommets «pairs»n'a pas de sommet avec une commande supérieure à 4a un nombre impair de sommets n'a pas de sommets d'ordre 3. Cette condition peut être expliquée si nous ne regardons qu'un seul sommet dans le graphique:

Ici, vous pouvez voir un seul sommet agrandi dans un graphique.
Si nous dessinons le graphique, nous aurons éventuellement un bord menant à ce sommet, puis un autre menant au loin. Cela fait que deux arêtes se rejoignent au sommet.
Peut-être que le sommet est un croisement plutôt qu'un coin. Dans ce cas, il y aura un autre bord menant vers le sommet et un autre bord menant. Nous avons maintenant quatre arêtes.
Et dans certains graphiques, il peut même y avoir une troisième paire d'arêtes menant vers et à partir du sommet. Maintenant, il y a six bords.
Notez que, de toute façon, il y a toujours un nombre pair d'arêtes se rejoignant au sommet.
Les deux seules exceptions sont les sommets où le chemin commence et où il se termine - ces deux peuvent avoir un nombre impair d'arêtes. Si les points de début et de fin sont identiques, tous les sommets du graphique sont pairs.

Si vous revenez sur la carte de Königsberg, vous verrez qu'il y a plus de deux îles avec un nombre impair de ponts. Par conséquent, un itinéraire qui traverse chaque pont exactement une fois est en effet impossible - et c'est ce que Leonard Euler a découvert.

La découverte d’Euler peut ne pas sembler particulièrement utile dans la vie réelle, mais les graphiques sont à la base de nombreux autres problèmes géographiques, tels que la recherche d’orientation entre deux lieux. Nous allons découvrir plus de ces applications plus tard.