éléments de théorie des graphes quelques exercices d'application

Éric SOPENA - sopena@labri.fr avril 2002 Éléments de théorie des graphes - Quelques exercices d'application (avec solutions) page 1 ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D'APPLICATION (AVEC SOLUTIONS) Le but principal de cette série d'exercices et de servir de " source d'inspiration ».
Bon nombre de ces exercices peuvent être
à
l'origine de toute une " famille » d'exercices
que l'enseignant n'aura aucun mal
à
" générer »...
Les exercices (ou questions) sont classés par niveau de difficulté :
(o) facile (oo) assez facile (ooo) difficile

Il est possible que certaines des solutions comportent des erreurs, de frappe ou
d'inattention... Merci au lecteur attentif de me les signaler...
1. NOTIONS DE BASE
1.1. Modélisation
Exercice 1. (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et
dont les arcs représentent la relation " être diviseur de ».
Solution Exercice 1. Aucune difficulté particulière (ne pas oublier les boucles)... 1

789101112
Exercice 2. (oo) Une chèvre, un chou et un loup se trouvent sur la rive d'un fleuve ; un passeur
souhaite les transporter sur l'autre rive mais, sa barque étant trop petite, il ne peut transporter qu'un
seul d'entre eux
à
la fois. Comment doit-il procéder afin de ne jamais laisser ensemble et sans
surveillance le loup et la ch
èvre, ainsi que la ch
èvre et le chou ?
Solution Exercice 2. Cette situation peut être modélisée à l'aide d'un graphe. Désignons par P le passeur, par
C la ch
èvre, par X le chou et par L le loup. Les sommets du graphe sont des couples précisant qui est sur la

rive initiale, qui est sur l'autre rive. Ainsi, le couple (PCX,L) signifie que le passeur est sur la rive initiale avec la

ch
èvre et le chou
(qui sont donc sous surveillance), alors que le loup est sur l'autre rive. Une arête relie deux
sommets lorsque le passeur peut passer (sic) d'une situation
à
l'autre. En transportant la ch
èvre, le passeur

passe par exemple du sommet (PCX,L) au sommet (X,PCL). Le graphe ainsi obtenu est biparti : les sommets
pour lesquels le passeur est sur la rive initiale ne sont reliés qu'aux sommets pour lesquels le passeur est sur

l'autre rive...
Éric SOPENA - sopena@labri.fr avril 2002 Éléments de théorie des graphes - Quelques exercices d'application (avec solutions) page 2 Naturellement, on ne considèrera pas les sommets dont l'une des composantes est CX ou LC car ces situations
sont interdites.
Il suffit ensuite de trouver un chemin (le plus court par exemple) entre la situation initiale (PCXL,-) et la situation
finale souhaitée (-,PCXL). La figure suivante donne un tel chemin : (PCXL,-)(PCL,X)(PCX,L)(PXL,C)(PC,XL)
(XL,PC)(C,PXL)(L,PCX)(X,PCL)(-,PCXL)
Exercice 3. (oo) Trois maris jaloux et leurs épouses souhaitent traverser une rivière. Ils disposent d'une
barque qui ne peut transporter plus de deux personnes
à
la fois. Comment doivent-ils procéder,
sachant qu'aucune femme ne doit rester en compagnie d'un ou deux hommes sans que son mari soit
présent ?
Montrez que ce probl
ème n'a pas de solution si les couples sont au nombre de 4.
Solution Exercice 3. La solution est donnée dans les vers suivants :
" It duplex mulier, nedit una, vehit que manentem ;
Itque una, utuntur tunc duo puppe viri.
Par vadit, redeunt bini ; mulierque so rorem
Ad vehit ; ad propriam sive maritus abit. »
Pour les non latinistes, il est possible d'utiliser le même principe que dans l'exercice précédent, en notant A, B

et C les femmes, a, b et c les maris. On
obtient encore un graphe biparti, selon que la barque est sur une rive
ou sur l'autre. Le schéma suivant propose une solution parmi d'autres (le graphe n'est pas représenté en