Les jeux des gendarmes et du voleur dans les graphes traitent de la<br />capture d'un voleur qui se déplace dans un réseau par une équipe de<br />gendarmes. Ces jeux trouvent leurs motivations en informatique<br />fondamentale, notamment dans le cadre de la théorie de la complexité<br />et dans celui de la théorie des mineurs de graphes. Ces jeux ont<br />également des applications en intelligence artificielle et en<br />robotique. Quel que soit le contexte, le nombre de gendarmes utilisés<br />a un coût et doit être minimisé. Dans cette thèse, nous étudions<br />diverses contraintes auxquelles les stratégies de capture sont<br />soumises, ainsi que le coût de ces contraintes en terme de nombre de<br />gendarmes. Nous distinguons principalement trois cadres d'étude.<br /><br />Dans la première partie de cette thèse, nous définissons une variante<br />de stratégie de capture qui établit un pont entre la largeur<br />arborescente et la largeur linéaire des graphes. En particulier, nous<br />prouvons la monotonie de cette variante générale et donnons un<br />algorithme exponentiel exact pour calculer de telles stratégies.<br /><br />Dans la seconde partie de cette thèse, nous nous intéressons aux<br />stratégies dites connexes qui doivent assurer que la partie propre du<br />réseau est constamment connexe. Nous prouvons plusieurs bornes<br />supérieures et inférieures du coût de cette contrainte en terme de<br />nombre de gendarmes. Nous étudions également la propriété de monotonie<br />des stratégies de capture connexe.<br /><br />Dans la troisième partie de cette thèse, nous étudions les stratégies<br />de capture dans un contexte décentralisé. Nous proposons plusieurs<br />algorithmes décentralisés qui permettent aux gendarmes de calculer<br />eux-mêmes la stratégie qu'ils doivent réaliser.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00168818 |
| Date | 02 July 2007 |
| Creators | Nisse, Nicolas |
| Publisher | Université Paris Sud - Paris XI |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0021 seconds