Graphes et réseauxLes ponts de Königsberg

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 et chaque pont reliant deux régions est représenté par un 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é:

Valeur

Petit et grand

Primalité

Parité

Ces graphes sont possibles :

Ces graphes ne sont pas possibles :

En comparant ces nombres pour des graphes possibles et impossibles, il semble qu'un graphe puisse être tracé s'il . 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 une arête arrivant à ce sommet, puis une autre partant de ce sommet. 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 une autre arête arrivant vers le sommet et une autre arête partant de ce sommet. Nous avons maintenant quatre arêtes.

Et dans certains graphiques, il peut même y avoir une troisième paire d'arêtes arrivant et partant du sommet. Maintenant, il y a six arête.

Notez que, de toute façon, il y a toujours un nombre pair d'arêtes qui 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 sommet 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.

Changer de langue

Connectez-vous à Mathigon

Partager

Réinitialiser la progression

Glossaire

Graphes et réseauxLes ponts de Königsberg

Map 1

Map 2

Map 3

Map 4