Le graphe G a 4 sommets : R 1 , R 2 , I 1 , I 2 reliés par 7 ponts : R 1 – I 1 : 2 ponts, R 1 – I 2 : 1 pont R 2 – I 1 : 2 ponts, R 2 – I 2 : 1 pont I 1 – I 2 : 1 pont Donner le degré de chaque sommet. Prouver qu'il est impossible de traverser chaque pont exactement une fois. Quel est le nombre minimal de ponts à ajouter pour qu'une chaîne eulérienne devienne possible ?

Problème du pont de Königsberg — généralisation

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Le graphe $G$ a 4 sommets : $R_{1}, R_{2}, I_{1}, I_{2}$ reliés par 7 ponts :

$R_{1}$ – $I_{1}$ : 2 ponts, $R_{1}$ – $I_{2}$ : 1 pont
$R_{2}$ – $I_{1}$ : 2 ponts, $R_{2}$ – $I_{2}$ : 1 pont
$I_{1}$ – $I_{2}$ : 1 pont

Donner le degré de chaque sommet.
Prouver qu'il est impossible de traverser chaque pont exactement une fois.
Quel est le nombre minimal de ponts à ajouter pour qu'une chaîne eulérienne devienne possible ?

Indices

— clique pour révéler

1 Indice 1

Le degre d'un sommet dans un graphe correspond au nombre total de ponts qui y arrivent : additionne, pour chaque sommet, tous les ponts qui le touchent.

2 Indice 2

Pour la question 2, rappelle-toi le theoreme d'Euler sur l'existence d'une chaine eulerienne : il faut compter combien de sommets ont un degre impair et comparer ce nombre a ce qu'exige le theoreme.

3 Indice 3

Pour la question 3, reflechis a l'effet de l'ajout d'un pont entre deux sommets impairs : cela change la parite de leur degre a tous les deux en meme temps, ce qui peut faire baisser le nombre total de sommets impairs de deux d'un coup.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Modélisation par graphe — réseau de villes Retour au chapitre Problème du voyageur de commerce — circuit hamiltonien optimal

Problème du pont de Königsberg — généralisation

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Problème du pont de Königsberg — généralisation

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯