Graphes eulériens

On dit qu'un graphe est eulérien s'il est possible de trouver un cycle passant une et une seule fois par toutes les arêtes.
On dit qu'un graphe est semi-eulérien s'il est possible de trouver une chaîne passant une et une seule fois par toutes les arêtes.
Plus simplement, on peut dire qu'un graphe est eulérien (ou semi-eulérien) s'il est possible de dessiner le graphe sans lever le crayon (et sans passer deux fois sur le même trait!).

Exercices

Exercice 1

Les graphes suivants sont-ils eulériens (ou semi-eulériens) ?

a.

b.

c.

d.

Exercice 2

Leonhard Euler (1707-1783)

Lors d'une promenade, est-il possible de passer sur tous les ponts de la ville une et une seule fois?

C'est un des problèmes fondateurs de la théorie des graphes, proposé par le mathématicien suisse Leonhard Euler en 1736.

Exercice 3

Donnez un critère permettant de dire à coup sûr si un graphe est eulérien.

Exercice 4

Soit G un graphe non eulérien. Est-il toujours possible de rendre G eulérien en lui rajoutant un sommet et quelques arêtes?

Exercice 5

Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des 16 segments de la figure suivante exactement une fois?

Exercice 6

On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5.

1. En excluant les dominos doubles, de combien de dominos dispose-t-on ?
2. Montrez que l'on peut arranger ces dominos de façon à former une boucle fermée (en utilisant la règle habituelle de contact entre les dominos).
3. Pourquoi n'est-il pas nécessaire de considérer les dominos doubles ?
4. Si l'on prend maintenant des dominos dont les faces sont numérotées de 1 à n, est-il possible de les arranger de façon à former une boucle fermée ?

Didier Müller, 2.2.03