Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Activités sur le chapitre 1
Graphes eulériens

 

Activité 1 - Graphes eulériens, modélisation par des graphes eulériens

Exercice 1 - Le lemme des poignées de mains

a. Serrez la main de certains éléments de votre groupe et notez le nombre N de mains que vous avez serrées, ainsi que le nom de ceux ou celles à qui vous avez serré la main.

b. Vérifiez que la somme des nombres N de tous les éléments de votre groupe est un nombre pair et que le nombre d'éléments pour lesquels N est impair est aussi un nombre pair.

c. Modélisez cette situation à l'aide d'un graphe dont les sommets sont les éléments de votre groupe et les arêtes... Que constatez-vous? Pouvez-vous énoncer des résultats généraux sur les graphes?

Remarque -  On peut envisager deux versions pour cette activité.

on serre la main de quelqu'un au plus une fois.

on peut serrer la main de quelqu'un plusieurs fois (il faut alors les compter toutes...), voire même serrer sa propre main, la main droite serrant la main gauche...

Quelle est la différence entre ces deux versions, pour le modèle envisagé?

Exercice 2 - Soit G un graphe. Le nombre d'arêtes partant d'un sommet est appelé le degré de ce sommet.

Quelles sont les propriétés de ce degré lorsque G est eulérien, semi-eulérien?

(Pour deviner ces propriétés, il est conseillé de dessiner des graphes puis de chercher s'ils sont eulériens ou semi-eulériens).

Quelques exemples :

 

Exercice 3 - En combien de passages sans lever le crayon peut-on dessiner le graphe ci-dessous?

 

Exercice 4 - Est-il possible, pour un cavalier, de parcourir un échiquier de telle sorte que, chaque fois qu'un chemin est possible entre deux cases, il passe exactement une fois sur ce chemin?

Répondre à la même question pour le roi et la tour.

Exercice 5 - On dit qu'un graphe est totalement eulérien si, de quelque manière que l'on essaye de tracer dessus un chemin eulérien, on y parvient. On dit qu'il est totalement eulérien à partir de v si ceci est vrai quand on part de v.

Voici le plan d'une exposition. Les organisateurs ont décidé de placer l'entrée au point v. Pourquoi est-ce une bonne idée? Existe-t-il d'autres endroits possédant la même propriété?

Exercice 6 - Soit G le graphe orienté dont les sommets sont les paires d'entiers 11, 12, 13, 21, 22, 23, 31, 32 et 33, deux sommets ij et kl étant reliés (de ij vers kl) si et seulement si k=j.

Représenter graphiquement G. Le graphe G est-il eulérien?

Prouver que l'on peut écrire une suite de 27 nombres, contenant neuf 1, neuf 2 et neuf 3, de telle sorte que chacun des 27 triplets 111, 112, , 333 possibles apparaisse dans cette suite exactement une fois.

Exercice 7 - Soit G un graphe simple (id est, sans boucle ni arêtes multiples), connexe et possédant n sommets (n 2). On rappelle que si s est un sommet de G, le degré de s, noté d(s) est égal au nombre d'arêtes qui partent de s.

(a) Montrer que, pour tout sommet s de G,

(b) En déduire qu'il existe forcément au moins deux sommets du graphe qui ont le même degré (Indication : si l'on range p+1 paires de chaussettes dans p tiroirs, l'un au moins des tiroirs contiendra plus d'une paire).

Exercice 8 - Est-il possible de dessiner un graphe simple à 6 sommets de telle sorte que les degrés de ceux-ci soient égaux à 5, 5, 5, 5, 3 et 3?

Exercice 9 - Soit n un entier 3. Quelle condition nécessaire et suffisante doit vérifier n pour que le graphe complet Kn soit eulérien?