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