Retour à la table des matières

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

 

Activités sur le chapitre 2
Graphes hamiltoniens

 

Activités sur le chapitre 2

Exercice 1 - On appelle tournoi un graphe orienté dans lequel, pour toute paire de sommets v et w, il existe exactement une arête les reliant (il s'agit donc soit de , soit de ).

Montrer que tout tournoi est semi-hamiltonien, c'est-à-dire qu'il existe un chemin, non nécessairement fermé, passant par chaque sommet exactement une fois. Donner un exemple de tournoi hamiltonien. Est-ce conforme à la logique sportive?

Exercice 2 - Un tournoi est dit ``sans surprise'' quand l'existence de deux arêtes et implique celle de l'arête .

Pourquoi une telle terminologie?

Montrer, en définissant les termes utilisés, que tout tournoi sans surprise admet un vainqueur et un classement.

Exercice 3 - Soit G un graphe à 13 sommets. On suppose qu'il est possible de colorier ces sommets en bleu et rouge de sorte que deux sommets adjacents ne soient jamais de la même couleur. Le graphe G est-il hamiltonien?

Exercice 4 - Les trois graphes ci-dessous sont-ils hamiltoniens?

Exercice 5 - Le n-cube Qn.

On appelle n-cube le graphe à 2n sommets, dont les sommets sont les n-uplets (a1, , an) formés de 0 ou de 1 (id est : chaque ai vaut 0 ou 1) et dont les arêtes sont définies de la manière suivante : deux sommets (a1, , an) et (b1, , bn) sont reliés par une arête si et seulement si les n-uplets correspondants ne diffèrent que par un terme.

Dessiner Q1, Q2, Q3 et Q4. Justifier la terminologie employée pour nommer ces graphes. Montrer que Qn est hamiltonien pour n 2.

Exercice 6 - ``Instant insanity''

On considère quatre cubes (il s'agit de vrais cubes, des dés par exemple), numérotés 1, 2, 3 et 4, et dont chacune des faces est coloriée par l'une des couleurs rouge, jaune, vert et bleu (qui seront abrégées en R, J, V etB). Le but du jeu est d'empiler les quatre cubes pour former une colonne, de telle sorte que sur chacune des quatre faces verticales de la colonne apparaisse chacune des quatre couleurs.

(a) Combien y-a-t-il de possibilités d'empiler ces quatre cubes (on considèrera comme identiques des empilements qui se déduisent l'un de l'autre par une rotation dans l'espace ou par une permutation des quatre cubes)?

(b) On considère le graphe G à quatre sommets et douze arêtes construit de la manière suivante : chaque sommet représente une couleur ; deux sommets sont reliés par une arête numérotée j (j = 1, 2, 3 ou 4) quand les deux couleurs correspondantes apparaissent sur deux faces opposées du cube numéro j. Montrer que, pour chaque valeur de j, il existe exactement trois arêtes portant le numéro j. (Les boucles sont autorisées).

(c) On empile les quatre cubes pour former une colonne. On désigne par G1 et G2 les sous-graphes de G dont les sommets sont les couleurs apparaissant sur les faces avant et arrière de la colonne (pour G1) et sur les faces droite et gauche pour G2, avec les arêtes associées. Montrer que chacun des sous-graphes G1 et G2 possède quatre arêtes, numérotées 1, 2, 3 et 4, et que ces deux graphes n'ont aucune arête en commun.

(d) Montrer que si l'empilement des quatre cubes est solution du jeu, chacun des graphes G1 et G2 contient les quatre sommets du graphe G et que chaque sommet est de degré 2 dans G1 et dans G2.

(e) Réciproquement, montrer que si le graphe G admet deux sous-graphes G1 et G2 ayant chacun quatre sommets et quatre arêtes numérotées différemment et n'ayant aucune arête en commun, le jeu admet une solution.

(f) Application.

 

Exercice 7 - Les missionnaires et les cannibales

Trois cannibales et trois missionnaires veulent traverser une rivière. Ils disposent d'une barque pouvant accueillir au plus deux personnes. Il y a une autre difficulté : à aucun moment, le nombre de cannibales présents sur l'une des rives ne doit excéder le nombre de missionnaires, faute de quoi ces derniers se trouveraient en grand danger. Aidez-les à traverser.

Indication : on pourra considérer le graphe orienté dont les sommets sont les couples (c,m), 0 c 3, 0 m 3, où c et m désignent respectivement les nombres de cannibales et de missionnaires sur la première rive (noter qu'il n'y a que dix paires admissibles sur les seize possibles). Deux sommets (c1,m1) et (c2,m2) sont reliés par une flèche rouge si on passe de l'état (c1,m1) à l'état (c2,m2) par un voyage en barque de la première à la seconde rive. Ils sont reliés par une flèche bleue si l'on passe du premier au deuxième par un voyage en barque de la seconde à la première rive. La solution du problème consiste à trouver un chemin orienté du sommet (3,3) au sommet (0,0) composé alternativement de flèches rouges et bleues.

Question subsidiaire : quel est le nombre minimal de traversées nécessaire?

Exercice 8 - Montrer que le graphe orienté étudié à la fin du chapitre précédent (algorithme de Sari) est hamiltonien. (Remarquer que les arêtes du graphe dont les sommets sont les suites de m ''0'' ou ''1'' peuvent se représenter au moyen du graphe dont les sommets sont les suites de m+1 ''0'' ou ''1'', et se rappeler que tous ces graphes sont eulériens).

Exercice 9 - Soit G un graphe simple (id est , sans boucle ni arêtes multiples), possédant n sommets (n 3). 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) On suppose qu'il existe dans G deux sommets a et b non adjacents et que, à cette restriction près, G possède le plus grand nombre possible d'arêtes. Combien G possède-t-il d'arêtes?

(b) On fait maintenant une hypothèse plus forte : les sommets a et b restent non adjacents, et de plus d(a) + d(b) n-1. Montrer que le nombre maximal d'arêtes de G est alors (n-1)(n-2)/2 + 1.

(c) On suppose que G possède (n-1)(n-2)/2 + 2 arêtes. Montrer que G est hamiltonien.

(d) Montrer, par un exemple, qu'il existe des graphes non hamiltoniens possédant n 3 sommets et (n-1)(n-2)/2 + 1 arêtes (un exemple simple serait le bienvenu).