Les ponts de Königsberg: naissance de la théorie des graphes
En quelques lignes, l’idée centrale et le résultat : le but de cette page est uniquement de comprendre l’essentiel (l’intuition et la conclusion principale) sans entrer dans tous les détails techniques.
Pour une explication complète, des exemples supplémentaires et une étude plus approfondie, consultez la page Théorie des graphes.
Le problème des ponts de Königsberg (1736) demande s’il est possible de traverser chacun des sept ponts d’une ville exactement une fois (et, dans une variante, de revenir au point de départ).
Euler répond négativement et introduit un geste décisif : remplacer la géographie par une structure de connexions. Cette modélisation fonde la théorie des graphes et met en évidence un critère simple (la parité des degrés) gouvernant l’existence de parcours eulériens.
L’histoire des mathématiques montre que des questions de la vie quotidienne peuvent conduire à l’invention d’objets abstraits. Le problème des ponts de Königsberg, posé comme défi de promenade, en est un exemple canonique : déterminer si l’on peut franchir chaque pont exactement une fois. La contribution d’Euler ne se réduit pas à une réponse d’impossibilité ; elle consiste surtout à dégager la structure combinatoire sous-jacente et à établir un critère général.
On considère quatre régions de terre séparées par un cours d’eau (deux rives et deux îles) reliées par sept ponts. La modélisation consiste à oublier les distances et formes géométriques : seules comptent les connexions. On associe un sommet à chaque région de terre et une arête à chaque pont reliant deux régions. Le problème devient : existe-t-il un parcours utilisant chaque arête exactement une fois ?
Cette réduction du spatial au relationnel est l’acte conceptuel fondateur : le résultat dépend uniquement de la structure d’adjacence, non d’une représentation géographique fidèle.
Un graphe est un couple $G=(V,E)$ où $V$ est un ensemble fini de sommets et $E$ un ensemble d’arêtes,
chaque arête étant un couple non ordonné $(u,v)$ avec $u,v$ dans $V$.
Dans l’exemple suivant, l’ensemble des sommets :
\[
V = \{A, B, C, D, E\}.
\]
Les arêtes sont :
\[
(A,B),\ (A,C),\ (A,D),\ (B,C),\ (D,E),\ (C,E).
\]
Dans cet exemple, on a considéré qu’une arête $e = (x,y)$ est la même que $(y,x)$.
On dit que le graphe n’est pas orienté.
Le degré d’un sommet $v$, noté $\deg(v)$, est le nombre d’arêtes incidentes à $v$.
Dans l’exemple suivant, $d(A) = d(\text{Gaz}) = 3,\quad d(C) = d(\text{Eau}) = 2,\quad d(B) = d(\text{Elec}) = 1.$
- Un chemin est une suite $(v_0,\ldots,v_k)$ telle que $(v_i, v_{i+1}) \in E$ pour tout $i$.
- Un cycle est un chemin fermé $v_0 = v_k$, dont toutes les arêtes sont distinctes.
- Le graphe est connexe si tout couple de sommets est relié par un chemin.
- Dans l’exemple suivant, $ABCD$ et $ABCAED$ sont des chaînes de longueurs respectives $3$ et $5$.
- $ABECBA$ est une chaîne fermée mais n’est pas un cycle.
- $ABCEA$, $ABECA$, $ACEBA$ et $ABCDEA$ sont des cycles.
Pour tout Graphe $G = (V,E)$ fini, on a :
\[
\sum_{v\in V}\deg(v) = 2|E|.
\]
En particulier, le nombre de sommets de degré impair est toujours pair.
- Chaque arête relie deux sommets du graphe. Donc elle est comptée exactement deux fois dans la somme de gauche.
- L’ensemble $I$ des sommets de degré impair et $P$ celui des sommets de degré pair forment une partition de $V$, donc :
\[
\sum_{A \in V} d(A) = \sum_{A \in I} d(A) + \sum_{A \in P} d(A) = 2\,\mathrm{Card}(E).
\]
Or $\displaystyle\sum_{A \in P} d(A)$ est pair. Donc $\displaystyle\sum_{A \in I} d(A)$ est pair.
Par suite, $\mathrm{Card}(I)$ est pair.
Dans l’exemple suivant, $\mathrm{Card}(E)=6$ et
\[
\begin{aligned}
\sum_{A \in V} d(A) &= d(A)+d(\text{Gaz})+d(C)+d(\text{Eau})+d(B)+d(\text{Elec}) \\
&= 3+3+2+2+1+1 \\
&= 2 \times 6.
\end{aligned}
\]
Le nombre de sommets de degré impair est 4.
- Un chemin eulérien est un chemin qui traverse chaque arête de G exactement une fois.
- Un circuit eulérien est un chemin eulérien fermé.
- Un graphe eulérien est un graphe qui possède un cycle eulérien.
Donc le graphe est eulérien.
Dans la configuration historique, les quatre régions (sommets) sont incidentes à un nombre impair de ponts: le graphe associé possède donc quatre sommets de degré impair. Par le Théorème 1, il ne peut exister alors un circuit eulérien (qui requiert 0 sommet impair). La promenade demandée est donc impossible.
La solution ne repose pas sur l’exploration exhaustive des itinéraires, mais sur un invariant simple : la parité des degrés. Cette méthode est généralisable à tout réseau modélisable par un graphe.
Le problème des ponts de Königsberg illustre la naissance d’une mathématique centrée sur les structures discrètes.
La théorie des graphes est aujourd’hui un langage fondamental pour modéliser des réseaux : transport, informatique, réseaux sociaux, biologie des interactions, et optimisation combinatoire. L’anecdote historique révèle un mécanisme typique : isoler l’essentiel, l’abstraire, puis en tirer des critères généraux.
- Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis.
- Biggs, N., Lloyd, E. K., Wilson, R. J. (1976). Graph Theory 1736–1936. Oxford University Press.
- Diestel, R. (2017). Graph Theory (5th ed.). Springer.
- Bondy, J. A. & Murty, U. S. R. (2008). Graph Theory. Springer.