Graphes eulériens : les ponts de Königsberg, les tracés d'un seul trait et les cycles - Exercice 1

20 min

Au XVIIIe siècle, la ville de Königsberg était traversée par une rivière qui formait une île

A

et séparait la rive nord

B

, la rive sud

C

et un autre quartier

D

. Sept ponts reliaient ces quartiers, comme sur le plan ci-dessous. Les habitants se demandaient s'il était possible de se promener en traversant chaque pont une et une seule fois. En 1736, Leonhard Euler a répondu à cette question.

Question 1

Modéliser la situation par un graphe dont les sommets sont les quartiers $A$ , $B$ , $C$ et $D$ , et dont les arêtes sont les ponts. Ce graphe est-il simple ?

Correction

Un graphe est dit

\red{\text{simple}}

si au plus une arête relie deux sommets et s'il n'y a pas de boucle sur un sommet.

Chaque pont relie deux quartiers : on obtient le graphe suivant.

Les ponts

1

2

relient tous les deux

A

B

, et les ponts

3

4

relient tous les deux

A

C

: deux sommets sont reliés par plusieurs arêtes, donc

le graphe n'est pas simple

Question 2

Donner le degré de chaque sommet.

Correction

On appelle

\red{\text{degré}}

d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois).

Le degré d'un quartier est le nombre de ponts qui y arrivent :

A

est relié aux ponts

1

2

3

4

5

;

B

aux ponts

1

2

6

;

C

aux ponts

3

4

7

;

D

aux ponts

5

6

7

. D'où :

Question 3

La promenade souhaitée par les habitants est-elle possible ?

Correction

Un graphe connexe possède une

\red{\text{chaîne eulérienne}}

si, et seulement si, le nombre de sommets de degré impair est égal à

0

2

Si le nombre de sommets de degré impair est égal à

2

, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.

Le graphe est connexe, mais ses quatre sommets sont de degré impair : il n'admet pas de chaîne eulérienne.
Finalement :

il est impossible de traverser chaque pont une et une seule fois

Question 4

On construit un huitième pont entre la rive nord $B$ et la rive sud $C$ . La promenade devient-elle possible ? Si oui, préciser où elle doit commencer et finir, puis proposer un itinéraire.

Correction

Le nouveau pont ajoute une arête entre

B

C

(en rouge) :

Les degrés deviennent :

A

5

;

B

4

;

C

4

;

D

3

.
Le graphe est connexe et deux sommets seulement ont un degré impair (

A

D

), donc le graphe admet une chaîne eulérienne (entre

A

D

).
La promenade doit commencer en

A

et finir en

D

(ou l'inverse). Par exemple :

A - B - A - C - A - D - B - C - D

, c'est-à-dire les ponts

1

2

3

4

5

6

, le nouveau pont, puis le pont

7

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.

Graphes eulériens : les ponts de Königsberg, les tracés d'un seul trait et les cycles - Exercice 1

Modéliser la situation par un graphe dont les sommets sont les quartiers AAA , BBB , CCC et DDD , et dont les arêtes sont les ponts. Ce graphe est-il simple ?

Donner le degré de chaque sommet.

La promenade souhaitée par les habitants est-elle possible ?

On construit un huitième pont entre la rive nord BBB et la rive sud CCC . La promenade devient-elle possible ? Si oui, préciser où elle doit commencer et finir, puis proposer un itinéraire.

Modéliser la situation par un graphe dont les sommets sont les quartiers $A$ , $B$ , $C$ et $D$ , et dont les arêtes sont les ponts. Ce graphe est-il simple ?

On construit un huitième pont entre la rive nord $B$ et la rive sud $C$ . La promenade devient-elle possible ? Si oui, préciser où elle doit commencer et finir, puis proposer un itinéraire.