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

15 min

Peut-on dessiner la figure ci-dessous d'un seul trait, sans lever le crayon et sans repasser sur un trait déjà tracé ? On la modélise par un graphe dont les sommets sont

A

B

C

D

E

(les deux diagonales du carré se croisent sans former de sommet).

Question 1

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).

Les degrés sont :

A

3

;

B

3

;

C

4

;

D

4

;

E

2

Question 2

Répondre à la question posée.

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.

Dessiner la figure d'un seul trait revient à trouver une chaîne eulérienne.
Le graphe est connexe et deux sommets seulement ont un degré impair (

A

B

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

A

B

).
Ainsi :

c'est possible, à condition de commencer en

A

et de finir en

B

(ou l'inverse)

Question 3

Proposer un tel tracé.

Correction

Par exemple :

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

Question 4

Peut-on dessiner cette figure d'un seul trait en revenant au point de départ ?

Correction

Un graphe connexe admet un

\red{\text{cycle eulérien}}

si, et seulement si, tous ses sommets ont un degré pair.

Il faudrait un cycle eulérien. Or les sommets

A

B

sont de degré impair, donc

ce n'est pas possible

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.