$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Dénombrements et probabilités > Théorie des graphes >

Ponts de Königsberg et cycle eulérien

  La ville de Königsberg est traversée par la rivière Pregolya, et comporte deux iles. Ces iles sont reliées entre elles et aux berges par des ponts, comme sur la figure ci-dessous. Est-il possible de passer d'une berge à l'autre de la ville en passant, une et une seule fois, par tous les ponts que la ville comporte? Est-il possible de passer une et une seule fois par chaque pont, et de revenir à son point de départ?

  Ces questions ont été étudiées par Euler, qui y a répondu par la négative. Le problème est que de chaque berge et de chaque ile partent un nombre impair de ponts. Pour que l'on puisse passer d'une berge à l'autre en passant par tous les ponts, il aurait fallu que d'au plus deux endroits partent un nombre impair de ponts. Pour que l'on puisse faire une boucle, il aurait fallu que de chaque berge et de chaque ile partent un nombre pair de ponts. Ceci se généralise aux graphes...

Modélisation par la théorie des graphes
Définition : On appelle degré d'un sommet d'un graphe (non orienté) le nombre d'arêtes partant de ce sommet.

Définition :
  • une chaine eulérienne est une chaine passant une et une seule fois par toutes les arêtes du graphe.
  • un cycle eulérien est une chaine eulérienne dont le sommet de départ et le sommet d'arrivée sont identiques.
Théorème :
  • Un graphe connexe possède une chaine eulérienne si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
  • Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

  Le problème des ponts de Königsberg peut se modéliser à l'aide d'un graphe de la façon suivante :
En particulier, de chaque sommet partent un nombre impair d'arêtes : il y a 4 sommets de degré impair. Ce graphe ne possède donc ni chaine eulérienne, ni cycle eulérien.

Königsberg fut la capitale de la Prusse. Cette ville s'appelle maintenant Kalingrad et est située en Russie. On dit parfois qu'Euler résolut ce problème car il aimait se promener dans la ville de Königsberg et particulièrement sur ses sept ponts. Mais, l'âge venant, il souhaitait raccourcir la longueur tout en franchissant tous les ponts!

Une version du théorème d'Euler existe aussi pour les graphes orientés. On démontre qu'un graphe orienté fortement connexe possède un cycle orienté eulérien si et seulement si de chaque sommet il part autant de somments qu'il en arrive.
Consulter aussi...