Éric SOPENA fr avril 2002

Eric Sopena

Description

Éric SOPENA - 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 2 3 4 5 6 7 8 9 10 11 12 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.

• fois des couples donnant le contenu du récipient


• composante connexe du sommet d'arrivée


• parcours du cavalier


• couple

Sujets

• Couple
• Problème du cavalier
• Sopeña

Informations

• Publié par: pefav
• Publié le: 01 avril 2002
• Nombre de lectures: 152
• Langue: Français

Extrait

Éric SOPENA - [e-mail] É LÉMENTS DE T HÉORIE DES G RAPHES   Q UELQUES EXERCICES D ’ APPLICATION   ( AVEC SOLUTIONS )

avril 2002

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. N OTIONS DE BASE   1.1. Modélisation Exercice 1.(o)graphe orienté dont les sommets sont les entiers compris entre 1 et 12 etConstruire un dont les arcs représentent la relation « être diviseur de ». Solution Exercice 1.Aucune difficulté particulière (ne pas oublier les boucles)… 1 12 2

10

11

9

3

5

4

8 6 7   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. par , d’un graphe. Désignons par P le passeur l’aideCette situation peut être modélisée à 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… Éléments de théorie des graphes - Quelques exercices d’application (avec solutions) page 1

Éric SOPENA - [e-mail] avril 2002 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)

  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 totalité)… (aAbBcC,-) (aAbBc,C) (aAbc,BC) (aAbB,cC) (ABC,abc) (AC,abBc)

  Dans le cas où quatre couples sont sur la berge, les sommets (aAbBcCdD,-) et (-,aAbBcCdD) sont dans des composantes connexes distinctes. Il n’existe donc pas de chemin de l’un à l’autre et le problème n’a pas de solution (on peut vérifier que dans la composante connexe du sommet d’arrivée, seuls figu rent des sommets correspondant àun seul mari sur la rive initiale)… À titre d’exercice supplémentaire, on peut voir que le problème des 4 maris jaloux a une solution s’il existe une île au milieu de la rivière permettant de déposer certaines personnes ou si la barque peut transporter trois personnes. Exercice 4.(oo)On souhaite prélever 4 litres de liquide dans un tonneau. Pour cela, nous avons à notre disposition deux récipients (non gradués !), l’un de 5 litres, l’autre de 3 litres... Comment doit-on procéder ? Solution Exercice 4.Toujours le même principe. Les sommets sont cette fois des couples donnant le contenu du récipient de 5 litres et celui du récipient de 3 litres. On place un arc entre deux sommets lorsqu’on peut passer d’une configuration à l’autre. On cherche alors un chemin du sommet 0,0 au sommet 4,0… La figure suivante montre un tel chemin (le graphe n’est pas représenté en entier…)

Éléments de théorie des graphes - Quelques exercices d’application (avec solutions)

page 2

Éric SOPENA - [e-mail] 0,0 5,0 2,3

4,0

0,3 2,0 4,3 5,3 Etc.

avril 2002

3,0 3,3 0,2 5,2   Exercice 5.(Jeu de Fan Tan) Deux joueurs disposent de 2 ou plusieurs tas d’allumettes. A tour de rôle, chaque joueur peut enlever un certain nombre d’allumettes de l’un des tas (selon la règle choisie). Le joueur qui retire la dernière allumette perd la partie. ¨(o) l’aide d’un graphe dans le cas où l’on dispose au départ de deuxModéliser ce jeu à tas contenant chacun trois allumettes, et où un joueur peut enlever une ou deux allumettes àchaque fois. ¨(oo)doit jouer le premier joueur pour gagner la partie àcoup sûr ?Que ¨(oo)avec 3 tas de 3 allumettes.Mêmes questions Solution Exercice 5.Le jeu avec 2 tas de trois allumettes est décrit par le graphe suivant (tous les arcs sont orientés de gauche àdroite) : 0,3 2,3 0,2  0,0 3,3 2,2  1,2  0,1 1,3 1,1   Le joueur qui atteint la configuration 0,0 perd la partie. Pour gagner, on doit donc atteindre la configuration 0,1 ou 0,2. On peut vérifier qu’en jouant 1,3 au premier coup, quelle que soit la réponse de l’adversaire, on peut atteindre ensuite 0,1 ou 0,2. Le coup gagnant au départ est donc « enlever 2 allumettes dans un tas ».   Pour trois tas de trois allumettes, c’est simplement un peu plus long ;-)… Exercice 6.Essayez d’exprimer (et non nécessairement de résoudre…) en termes de graphes les problèmes suivants : ¨(o)sur un échiquier sans qu’aucune d’elles ne puisse enPeut-on placer huit dames prendre une autre ? ¨(o)Un cavalier peut-il se déplacer sur un échiquier en passant sur chacune des cases une fois et une seule ? ¨(o)sur un échiquier 5x5 afin de contrôler toutes lesCombien doit-on placer de dames cases ? Solution Exercice 6.Pour chacune de ces questions, on construit un graphe dont les sommets représentent les cases de l’échiquier. Les arêtes sont alors définies ainsi : 1 et 3 : une arête relie deux cases si une dame placée sur l’une contrôle l’autre, 2 : une arête relie deux cases si un cavalier placée sur l’une peut se rendre sur l’autre. Les 3 problèmes s’expriment alors ainsi en terme de graphes : 1 : Trouver un ensemble maximal de sommets tels qu’il n’existe aucune arête entre ces sommets (un tel ensemble est ditindépendant). 2 : Trouver un cheminhamiltonien (c’est-à-dire un chemin passant une et une seule fois par chacun des sommets). 3 : Trouver un ensemble minimal de sommets tel que tout sommet appartient à cet ensemble ou est relié par une arête àau moins l’un des sommets de cet ensemble (un tel ensemble est ditdominant).

Éléments de théorie des graphes - Quelques exercices d’application (avec solutions)

page 3