50 clés pour comprendre les maths
116
chronologie
1735
Euler résout le problème
des ponts de Königsberg.
1874
Carl Schorlemmer établit
un lien entre la chimie et
les « arbres ».
Königsberg est une ville de la Prusse Orientale bien connue pour ses sept ponts qui
traversent le fleuve Pregolia. Ville de l’illustre philosophe Emmanuel Kant, elle est
aussi, grâce à ses ponts, liée au célèbre mathématicien Leonhard Euler.
Au xviii
e siècle, on se posa une question étrange : était-il possible de faire le tour de
Königsberg en passant une fois et une seule par chacun de ses ponts ? Il n’est pas
nécessaire de revenir à notre point de départ au terme de
cette promenade, mais en revanche, chaque pont
doit être traversé une fois et une seule.
En 1735, Euler présenta la solution de ce problème à l’Académie Russe, solution qui est à
l’origine de la théorie moderne des graphes.
Dans notre représentation, l’île du milieu du
fleuve est appelée I et les berges du fleuve A, B,
et C. Pouvez-vous concevoir un itinéraire pour
une promenade dominicale qui permette de traverser chaque pont une fois et une seule ? Prenez
un crayon et essayez. La solution est de passer d’une
représentation semi-abstraite à une représentation totalement abstraite.
En procédant ainsi, on obtient un graphe constitué de points appelés
« sommets » et de lignes appelées « arêtes » ou « arcs ». Les
berges sont représentées par les sommets, et les ponts qui
les relient par les arêtes. Peu importe qu’elles ne soient
pas droites ou qu’elles soient de longueurs différentes.
Ce n’est pas l’essentiel. Seules les connections nous intéressent.
Euler fit remarquer la chose suivante : à part au début et à la fin
d’un tel itinéraire, à chaque fois que l’on traverse un pont, on doit
Il existe deux types de graphes en mathématiques. À l’école, on trace des courbes
qui montrent la relation entre deux variables x et y. Il existe une catégorie
de graphes découverte plus récemment où des points sont reliés entre eux par
des arêtes.
Les graphes
29
A
I
B
C
A
I
B
C
116
chronologie
1735
Euler résout le problème
des ponts de Königsberg.
1874
Carl Schorlemmer établit
un lien entre la chimie et
les « arbres ».
Königsberg est une ville de la Prusse Orientale bien connue pour ses sept ponts qui
traversent le fleuve Pregolia. Ville de l’illustre philosophe Emmanuel Kant, elle est
aussi, grâce à ses ponts, liée au célèbre mathématicien Leonhard Euler.
Au xviii
e siècle, on se posa une question étrange : était-il possible de faire le tour de
Königsberg en passant une fois et une seule par chacun de ses ponts ? Il n’est pas
nécessaire de revenir à notre point de départ au terme de
cette promenade, mais en revanche, chaque pont
doit être traversé une fois et une seule.
En 1735, Euler présenta la solution de ce problème à l’Académie Russe, solution qui est à
l’origine de la théorie moderne des graphes.
Dans notre représentation, l’île du milieu du
fleuve est appelée I et les berges du fleuve A, B,
et C. Pouvez-vous concevoir un itinéraire pour
une promenade dominicale qui permette de traverser chaque pont une fois et une seule ? Prenez
un crayon et essayez. La solution est de passer d’une
représentation semi-abstraite à une représentation totalement abstraite.
En procédant ainsi, on obtient un graphe constitué de points appelés
« sommets » et de lignes appelées « arêtes » ou « arcs ». Les
berges sont représentées par les sommets, et les ponts qui
les relient par les arêtes. Peu importe qu’elles ne soient
pas droites ou qu’elles soient de longueurs différentes.
Ce n’est pas l’essentiel. Seules les connections nous intéressent.
Euler fit remarquer la chose suivante : à part au début et à la fin
d’un tel itinéraire, à chaque fois que l’on traverse un pont, on doit
Il existe deux types de graphes en mathématiques. À l’école, on trace des courbes
qui montrent la relation entre deux variables x et y. Il existe une catégorie
de graphes découverte plus récemment où des points sont reliés entre eux par
des arêtes.
Les graphes
29
A
I
B
C
A
I
B
C