Localisation d’un robot dans un graphe - Lycée Condorcet (Montreuil) Lycée Jean Jaurès (Montreuil), Association Science Ouverte (Bobigny)

Différencier tous les points quelconques d'un graphe à l'aide de balises. Il s'agit de l'objectif de ce problème. En d'autres mots: permettre à un Un robot qui se déplacerait sur les nœuds d'un graphe de se repérer à chaque instant, simplement en sachant sa distance aux différentes balises initialement placées sur des nœuds.
Bien entendu, la question cruciale est: où placer les balises? Combien en placer? Si on considère que le coût des balises est conséquent, il faut chercher à en minimiser le nombre, et donc, à pouvoir déterminer des méthodes pour placer intelligemment les balises.
A travers l'étude de nombreux types de graphes différents, les élèves présenteront les résultats auxquels ils ont abouti.