Identification des sommets dans les graphes

Identification des sommets dans les graphes

Les codes identifiants ont été introduits par M.G. Karpovsky, K. Chakrabarty et L.B. Levitin dans l’article séminal [65], afin de modéliser la détection et localisation de pannes dans les réseaux multi-processeurs. En un peu plus d’une dizaine d’années, ils ont donné lieu à de nombreuses publications (plus d’une centaine à ce jour) ; on pourra consulter une bibliographie quasi-exhaustive, méticuleusement maintenue à jour par A. Lobstein, à l’adresse électronique [73]. Cette liste recense aussi les articles concernant les codes localisateurs-dominateurs, une notion antérieure et assez proche (voir 1.5.1 à ce su- jet). Citons également la thèse de J. Moncel ([74]) qui constitue une bonne introduction au sujet.Les définitions concernant les codes identifiants et graphes sans jumeaux se trouvent dans le chapitre 1 ; nous ne pourrons y faire un état de l’art complet mais présenterons les résultats fondamentaux, ainsi que ceux directement liés à nos travaux. Les résultats de ce chapitre concernent essentiellement le cardinal minimal d’un code identifiant dans un graphe : nous y verrons quelques bornes inférieures et supérieures, ainsi que quelques graphes où ce cardinal minimal est connu exactement (ou presque). Les questions relatives aux graphes sans jumeaux, intrinsèquement liés aux codes identifiants, seront abordées dans le chapitre 2, puis le chapitre 3 traitera de la question de la complexité algorithmique du calcul de codes identifiants. Enfin, le chapitre 4 présente une nouvelle notion, celle des systèmes de contrôle, qui constitue une généralisation de la notion de code identifiant. Rappelons que la plupart des preuves de nos résultats ne seront pas données ici mais peuvent être consultées dans les annexes en troisième partie de cette thèse.

Les codes identifiants ont été introduits afin de modéliser des problèmes de localisation dans des réseaux, par exemple la recherche de pannes dans les systèmes de processeurs ([65]). Une autre application possible est la détection et localisation d’un incendie dans un bâtiment ([81]), que nous allons ici utiliser pour présenter le problème.Prenons l’exemple d’un musée, représenté sur la figure 1.I (partie gauche), que nous voulons équiper de détecteurs de fumée. Ce musée est composé de huit pièces dénommées selon les huit premières lettres de l’alphabet ; certaines de ces pièces communiquent par une porte et d’autres non. Nous modélisons ce musée par un graphe Gcomportant huit sommets correspondant chacun à une pièce ; deux sommets de ce graphe sont reliés par une arête si et seulement si les deux pièces correspondantes du musée communiquent par une porte. Ce graphe est également représenté sur la figure 1.I (partie droite).Le cadre étant posé, supposons que nous disposions de détecteurs de fumée dont chaque pièce puisse être équipée. Ces détecteurs ont une portée d’une pièce, c’est-à-dire qu’ils détecteront de la fumée si un feu se déclare dans la pièce où ils se trouvent, ou dans une pièce immédiatement adjacente. Par exemple, un détecteur placé dans la pièce G pourra détecter si un feu se déclare dans les pièces E, F , G et H ; en revanche il ne détectera pas un feu en B ou en D. Le concept mathématique correspondant à celui d’un détecteur defumée est celui de mot de code. Nous indiquons le choix d’un mot de code sur les figures en noircissant le sommet correspondant. Nous dirons ainsi par exemple que les sommets e, f , g et h sont couverts par le mot de code g : voir la figure 1.II.

Déterminer un ensemble dominant de cardinal minimum dans un graphe donné est un problème difficile (voir le paragraphe 1.5.1). Ici, nous voulons cependant faire plus que surveiller l’intégralité du musée : nous voulons être capables de localiser les feux. Pour cela, supposons qu’au poste de commandement du gardien de musée se trouvent des voyants lumineux, un par détecteur de fumée, ces voyants s’allumant si le détecteur correspondant détecte de la fumée. En reprenant l’exemple de la figure 1.III, et en supposant qu’il y ait au plus un départ d’incendie dans notre musée, dressons une table indiquant, pour chaque pièce où un feu pourrait se déclarer, quels voyants s’allumeraient dans ce cas (table 1.I)., nous dirons que le code choisi, à savoir C = {b, c, g}, n’est pas suffisant pour séparer le sommet b du sommet c. Le même problème se présente avec les trois sommets f , g et h. Il nous faut pour ce faire davantage de mots de code, réalisant ainsi ce que nous appellerons un code identifiant, c’est-à-dire un choix de mots de code tel que la table correspondante, en plus de ne pas comporter de lignes vides, ne contienne pas deux lignes égales. Pour ce graphe, il nous faut au minimum quatre mots de code afin de réaliser un code identifiant. Un exemple optimal est donné sur la figure 1.IV, et on pourra vérifier les conditions requises pour être un code identifiant sur la table 1.II.