Universit Paris 13 Sup Galile INFO2Institut Galile Anne
2011-2012
Algorithmique de GraphesTD1 : Modlisation
Exercice 1Coupe du monde de rugby !
Le slectionneur des lignes arrires doit choisir 7 joueurs pour
les 7 postes (Pour information, undemi de mle, un demi douverture,
deux ailiers, deux centres et un arrire.). Nous appelleronsP1, P2,
et ainsi de suite jusqu P7 les 7 postes. Il dispose de 7 joueurs,
de J1 J7. Certainsde ces joueurs sont polyvalents, dautres non.Cest
ainsi que J1 ne peut jouer quau poste P1. J2 peut occuper sans
problme les postes P2ou P3. J3 peut jouer aux postes P3, P4 ou P5,
J4 au poste P6, J5 au poste P5, J6 aux postesP5 ou P7 et enfin J7
aux postes P5 ou P6.
1. Dessiner un graphe dont les 14 sommets correspondront aux 7
joueurs et aux 7 postes.Utiliser ce graphe pour traduire les
relations "joueurs-postes" nonces ci-dessus.
2. Montrer quavec les 7 joueurs slectionns ci-dessus, il est
impossible de composer lquipe.
3. Le slectionneur remplace J5 par un autre joueur qui, lui,
peut occuper les postes P2, P3ou P5. Montrer que cette fois une
quipe est possible. En donner la composition.
Exercice 2Est-il possible de concevoir un appartement de quatre
pices sur un seul tage de faon que lonpuisse passer dune pice
quelconque nimporte quelle autre pice sans passer par une
piceintermdiaire, quelle quelle soit, mme un couloir ou un simple
placard, qui sont ici considrscomme des pices part entire ? Quen
est-il dun appartement 5 sommets ?
Exercice 3Inquations et graphes
Considrer le systme dinquations suivant :
x1 + x2 1
x1 + x3 + x4 1
x4 + x5 1
o x1, x2, x3, x4 et x5 sont des variables bivalentes.Dterminer
une solution de ce systme qui maximise la fonction :z = x1 + x2 +
x3 + x4 + x5Pour cela, poser le problme comme celui de la recherche
dun ensemble particulier de sommetsdans un graphe.
Exercice 4Soient un rcipient de 8 litres, plein deau, et deux
rcipients vides de contenances respectives5 et 3 litres. Comme,
chaque manipulation, on ne peut que remplir ou vider totalement
undes rcipients disponibles, est-il possible de partager
quitablement les 8 litres en 2 fois 4 litres ?
Exercice 5On lance trois fois de suite une pice de monnaie
parfaitement quilibre. A chaque lancer, ona deux rsultats possibles
: pile (P) ou face (F).Reprsenter sous la forme dun arbre tous les
rsultats possibles, qui sont donc au nombre dehuit. Cet arbre vous
permettra de rpondre des questions concernant le calcul des
proba-bilits. Par exemple, combien a-t-on de chances dobtenir
exactement deux fois pile sur troislancers ?
1
Exercice 6Le jeu du piquet cheval
Le piquet cheval est un trs vieux jeu franais qui est une
version simplifie du jeu de NIMet dispose de nombreuses variantes.
Avec un seul tas de 21 jetons, deux joueurs chacun leurtour
prennent 1 ou 2 jetons. Le joueur qui ramasse le dernier jeton a
gagn.
1. Combien de jetons doit prendre le premier joueur pour avoir
une chance de gagner ?
2. Que se passe-t-il si maintenant celui qui ramasse le dernier
jeton a perdu ?
Exercice 7Pauvre paysan au bord dune rivire, il dsire faire
passer de lautre ct un loup, une chvreet un chou. Sa barque ne peut
embarquer quun de ces trois passagers. Naturellement, il nepeut pas
laisser seuls le loup et la chvre, ni la chvre et le chou. Un
graphe pourrait-il aiderle paysan ?
2
