TIPE_EL-HASSAR_Ibtissame.pdf

Analyse stratégique du jeu des policiers et du voleur EL-HASSAR Ibtissame KE028M Plan Introduction 3 Notions de la théorie des graphes 4 Le jeu de policiers et du voleur 12 Caractérisation d'un graphe policier gagn...

Analyse stratégique du jeu des policiers et du voleur EL-HASSAR Ibtissame KE028M Plan Introduction 3 Notions de la théorie des graphes 4 Le jeu de policiers et du voleur 12 Caractérisation d'un graphe policier gagnant 14 Stratégie de policier gagnant dans les arbres 20 Nombre minimal de policiers 24 Conclusion 28  Introduction PAC-MAN GTA San Andreas 3 Théorie des graphes 4 Graphe non orienté 5  Boucle, chaîne, cycle Boucle Chaîne Cycle 6 Graphe complet 7 Sous graphe 8 Voisinage d'un sommet 9  Graphe connexe Graphe connexe Graphe non connexe 10  Arbre Un arbre est un graphe connexe sans cycle 11  Le jeu de policiers et du voleur 12 Présentation du jeu 01 Chaque joueur occupe un sommet. Un joueur peut passer d'un sommet à un 02 autre si ces deux sommets sont liés par une arête du graphe. Chaque joueur peut utiliser une arête au plus 03 pour se déplacer. Le jeu commence par le choix d'un sommet du 04 graphe par le policier. Le jeu se termine si les deux joueurs 05 occupent le même sommet. 13 Caractérisation d'un graphe policier gagnant 14  Premiers résultats Un graphe non connexe est voleur gagnant. Un graphe complet est policier gagnant. 15  Premiers résultats Tout cycle de longueur n⩾4 est voleur gagnant. Tout arbre fini est policier gagnant. 16 Premiers résultats 17 Premiers résultats 18  Premiers résultats Graphe démontable donc graphe policier gagnant Graphe non démontable donc graphe voleur gagnant 19 Stratégie de policier gagnant dans les arbres 20  Stratégie de policier gagnant dans les arbres Positionner le policier à la racine de l’arbre Si le voleur est dans le Si le voleur est dans le sous arbre droit sous arbre gauche Le policier se déplace Le policier se déplace vers le fils droit vers le fils gauche 21 Stratégie de policier gagnant dans les arbres 22 Stratégie de policier gagnant dans les arbres 23 Nombre minimal de policiers 24 Nombre minimal de policiers 25 Nombre minimal de policiers 26 Nombre minimal de policiers 27  Conclusion 01 02 03 04 Analyse et Identification Relation entre Axes étude des des stratégies types de d’améliorations graphes gagnantes graphes et nombre de policiers 28 Merci de votre attention EL-HASSAR Ibtissame KE028M Annexe Exemple de code pour tracer un graphe en Python 31 Exemple de code pour tracer un graphe en Python 32 Caractérisation d'un graphe policier gagnant 33 Caractérisation d'un graphe policier gagnant 34 Nombre minimal de policiers 35 Nombre minimal de policiers 36 Nombre minimal de policiers 37 Nombre minimal de policiers 38 Stratégie de policier gagnant dans les arbres 39 Stratégie de policier gagnant dans les arbres 40  Références : ttps://fr.wikipedia.org/wiki/Pac-Man : Amal El Quarari, Jeu de poursuite sur graphe non rflexif, Mémoire présenté à la Faculté des études supérieures en vue de l'obtention du grade de Maître ès sciences (M.Sc.) en informatique : Héli Marcoux, Jeux de poursuite policier-voleur sur un graphe Le cas du voleur rapide, 2014. : Anthony Bonato Richard J. Nowakowski, The Game of Cops and Robbers on Graphs 41