Codes identifiants dans les graphes
De Ensiwiki.
Sommaire |
Codes identifiants dans les graphes
| Labo | Laboratoire G-SCOP |
| Equipe | Recherche Opérationnelle et Planification de la Production |
| Encadrants | julien.moncel@g-scop.inpg.fr
|
Thème général : codes identifiants
Un sommet mystère (appelons-le x) se cache (peut-être) dans un graphe donné G. Pour savoir où se cache le sommet mystère, on a le droit d'interroger les sommets du graphe. Si on interroge un sommet v, on lui demande ``est-ce que tu vois le sommet mystère x ? Le sommet v répond alors ``oui ou ``non, sachant que ``voir un sommet signifie être voisin de ce sommet ou être soi-même ce sommet.
Un code identifiant d'un graphe est un sous-ensembles de ses sommets, C, tel que si on interroge tous les sommets de C alors on peut soit certifier qu'il n'y a pas de sommet mystère caché dans le graphe, soit affirmer qu'il y a un sommet mystère, et dire qui c'est.
Si un tel code existe, le problème est en général de déterminer un code identifiant de cardinalité minimum. Le problème est NP-difficile en général, et il existe des algorithmes polynomiaux pour quelques classes de graphes, comme par exemple les arbres. Les codes identifiants ont été introduits il y a 10 ans pour modéliser des problèmes de détection de défaillances dans les réseaux.
Compétences attendues
Bases en théorie des graphes, et éventuellement programmation dans un langage au choix.
Contexte du travail
Dans ce projet on pourra s'intéresser aux deux questions suivantes.
1) Dans l'hypercube
Les hypercubes et puissances d'hypercubes sont des graphes particulièrement étudiés pour ce problème. Un hypercube de dimension n a pour ensemble de sommets les mots binaires de longueur n, et il y a une arête entre deux mots s'ils diffèrent en exactement un bit. Ainsi 01001 et 01011 sont deux sommets voisins de l'hypercube de dimension 5. La puissance d'ordre k d'un graphe G est un graphe dont les sommets sont les sommets de G, et tel qu'il y a une arête entre u et v si il existe un chemin d'au plus k arcs entre u et v dans G. Notons Q_n^k la puissance d'ordre k de l'hypercube de dimension n.
On s'intéresse à la conjecture suivante :
si k est fixé, alors la cardinalité minimum d'un code identifiant de Q_n^k croît avec n
Autrement dit, plus mon hypercube (ou ma puissance d'hypercube) est gros, plus il me faut de sommets pour détecter le sommet mystère. Evident, non ?
Cette conjecture de Blass, Honkala et Litsyn date de 2001 ; en 2006 elle a été
démontrée dans le cas k=1 par l'encadrant de ce projet, en utilisant un argument
de projection très simple (la preuve fait une page). Cet argument devrait pouvoir
être adapté au cas général où k >= 2 (en tous les cas, c'est l'impression de
l'encadrant du projet !).
2) Dans la grille
Les grilles sont également des graphes très étudiés pour ce problème. Cependant, on ne connaît pas la cardinalité optimale d'un code identifiant de la grille 3 x n (ni d'ailleurs la cardinalité optimale des grilles k x n pour k >= 3). En fait les résultats exacts ne sont connus que pour les grilles 1 x n et 2 x n... Un peu light, non ? Ne pourrait-on pas s'inspirer de ce qui a été fait pour les grilles 1 x n et 2 x n pour déterminer l'optimum pour les grilles 3 x n ? en fait, nous conjecturons que pour une grille infinie de hauteur 3, la densité optimale d'un code identifiant est 2/5.
Sujet
L'étudiant intéressé pourra s'attaquer, au choix, au problème 1) Dans l'hypercube ou au problème 2) Dans la grille.
Résultats attendus
Nous visons dans ce TER à la résolution d'un des deux problèmes ci-dessus. Des résultats partiels significatifs sont un minimum. Pour le problème 2), il pourra être judicieux d'utiliser d'outil informatique pour vérifier des enchainements de blocs.
