Code identifiant d'un graphe

Code couvrant : Tout sommet blanc est voisin d’au moins un sommet noir : Le sous-ensemble des sommets noirs est un code couvrant du graphe.

Soit ${\displaystyle G=(V,E)}$ un graphe non orienté et C un sous-ensemble de sommets du graphe G. Si C est tel que tout sommet v de V est voisin d’au moins un sommet de C, on dira alors que C est un code couvrant de G. Un code couvrant est aussi appelé dominant du graphe. Pour un sommet v de G, on définit le voisinage étendu de v comme l’ensemble :

${\displaystyle \mathbb {N} (v)=N(v)\cup V}$

Un sous-ensemble de sommets C est un code couvrant de G si et seulement si pour tout v ∈ V on a :

${\displaystyle \mathbb {N} (v)\cap C\neq \varnothing }$

On dira qu’un sommet c ∈ C couvre le sommet v s’il appartient au voisinage étendu de v.

Un sous-ensemble C’ de sommet du graphe G est un code séparateur de G si et seulement si :

${\displaystyle \forall (u,v)\in G,u\neq v,N(u)\cap C'\neq N(v)\cap C'}$

ce qui est équivalent à dire :

${\displaystyle \forall (u,v)\in G,u\neq v,N(u)\cap C'}$ Δ ${\displaystyle N(v)\cap C'}$

Où Δ désigne la différence symétrique de deux ensembles: A Δ B = (A\ B) ∪ (B\ A) = (A∪ B) \ (A ∩ B)

On dira qu’un sommet c ∈ C sépare les sommets u et v s’il appartient à la différence symétrique de ${\displaystyle N(v)\cap C}$ et ${\displaystyle N(v)\cup C}$.

Autrement dit, un code séparateur de G sépare toutes les paires de sommets distincts du graphe G.

La recherche d’un code séparateur d’un graphe G revient à résoudre un problème de couverture par tests dont l’instance est la matrice d’adjacence de G.

Un sous-semble C de sommets de G qui est à la fois un code couvrant et un code séparateur est appelé un code identifiant de G. Tous les sommets du graphe G sont donc couverts et séparés. On appelle pour chaque sommet v ensemble identifiant l’ensemble ${\displaystyle N(v)\cap C}$. On notera cet ensemble ${\displaystyle L(v,C)}$ ou ${\displaystyle L(v)}$.

On a donc C qui est un code identifiant de G si et seulement si l’application :

${\displaystyle V\rightarrow \;L(v,C)}$

est une injection dont l’image ne contient pas l’ensemble vide.

Comme nous l’avons mentionné plus haut, les codes identifiants ont été introduits pour modéliser un problème pratique d’identification de processeurs défectueux dans des réseaux multiprocesseurs.

On suppose que chaque processeur p d’un réseau soit capable d’exécuter une procédure test(p), qui s’applique à p ainsi qu’aux processeurs voisins de p. La procédure test(p) teste le bon fonctionnement de p ainsi que celui de ses voisins, et retourne une réponse de type binaire : 0 si une défaillance a été détectée sur p ou sur l’un de ses voisins, et 1 sinon. En supposant qu’à tout moment, au plus un processeur du réseau soit défectueux, le problème est de déterminer un sous ensemble de processeurs C tel que :

• Si au moins un des processeurs de C renvoie 0 après l’exécution de test, alors il y a un unique processeur défectueux dans le réseau, que nous sommes en mesure de localiser d’après les résultats des exécutions de test sur C
• Si tous les processeurs de C renvoient 1 après l’exécution de test, alors tous les processeurs du réseau sont en bon état de marche

Il est facile de voir qu’un sous-ensemble de processeurs C vérifie ces deux conditions si et seulement si l’ensemble de sommets correspondant C est un code identifiant du graphe associé au réseau.

Si aucun processeur du réseau n’est défectueux alors C est un code couvrant du graphe associé au réseau.

La première condition veut dire que C est un code séparateur du graphe. En effet, le sous-ensemble des processeurs de C voisin du processeur défectueux p : c’est l’ensemble identifiant de p.

Le problème est de retrouver une pièce où un incendie s’est déclaré grâce aux réponses données par les détecteurs placés dans certaines pièces. Cela revient à chercher un sommet particulier, s’il existe, parmi tous les sommets d’un graphe G donné. On suppose que si un tel sommet existe il est unique. Savoir où placer les détecteurs revient à savoir quels sommets du graphe questionner. Pour cela nous allons choisir un ensemble C de sommets à « interroger », en posant la question suivante au sommet choisi : « existe-t-il un sommet en feu dans ton voisinage ? » :

• Si la réponse est 1 (oui), le sommet en feu peut être tout aussi bien lui que l’un de ses voisins.
• Si la réponse est 0 (non), on peut affirmer qu’il n’y a pas de sommet en feu dans l’ensemble C.

En supposant que C est un code identifiant, alors : après avoir interrogé tous les sommets du graphe, on puisse toujours affirmer : « il y a un sommet en feu et c’est celui-là » ou bien « il n’y a pas de sommet en feu dans ce graphe », et ce, quel que soit l’endroit où l’incendie peut se déclarer.

Le problème de détection de feu : Plan des pièces, et son graphe associé.

En prenant l’exemple de la figure, si on décide d’interroger un ensemble de sommet C (les sommets en noir) du graphe G et on aura les réponses suivantes :

Ces réponses nous permettent d’affirmer qu’il y a au moins un sommet en feu, qui est voisin à la fois du sommet « 6 » et du sommet « 8 »; il y a donc seulement deux possibilités : l’un (ou plusieurs) des sommets « 1 » et « 2 » « 7 » « 8 » est en feu. Or les sommets « 2 » et « 7 » sont voisins du sommet « 5 » dont la réponse est non, ce qui exclut ces deux sommets, donc les sommets en feu sont les sommets « 1 » et « 8 ». Pour que l’ensemble C soit un code identifiant, il faut qu’il fonctionne pour retrouver n’importe quel sommet en feu.

cas du jeu Qui est-ce ?

Le problème de recherche d’un sommet particulier (processeur défectueux ou pièce en feu) peut aussi s’appliquer sous une forme adaptative. Contrairement à la recherche d’un code identifiant où les sommets de l’ensemble sont interrogés un par un successivement, il s’agit ici d’adapter le code au fur et à mesure des réponses données. Dans ce cas, la recherche d’une solution optimale revient à minimiser le nombre d’interrogations. À l’image de nombreux jeux de devinettes populaires ou de jeux commerciaux comme le « Qui est-ce ? », expliqué dans ce qui suit :

• des personnes : a, b, c, d, e, f ;
• des caractéristiques : femme, jeune, lunettes ;
• les caractéristiques qui identifient le personnage mystère : il est jeune, mais ce n’est pas une femme.

• Mark G Karpovsky, Krishnendu Chakrabarty et Lev B. Levitin, « On a new class of codes for identifying vertices in graphs », Information Theory, IEEE Transactions on, vol. 44, n^o 2,‎ 1998, p. 599-611 (lire en ligne)
• T. LEHOUILLIER, Codes identifiants dans les graphes, Travaux Études Recherches, Grenoble INP-ENSIMAG, 2009-2010.
• F. FOUCAUD, S. GRAVIER, R. NASERASI, A. PARREAU, P. VALICOV. Identifying codes in line graphs. LaBRI, Université de Bordeaux, CNRS. 2011. https://arxiv.org/abs/1107.0207
• F. FOUCAUD, R. NASERASR et A. PARREAU, Characterizing external digraphs for identifying codes and external cases of Bondy’s theorem on induced subsets. Graphs and Combinatorics manuscript. January 2012. http://www.lri.fr/~reza/pdfs/MaxIDCodeDigraph.pdf
• S. RAY, R. UNGRANGSI, F. De PELLEGRINI, A. TRACHTENBERG, et D. STAROBINSKY, Robust Location Detection in Emergency Sensor Networks, 2003. http://ipsit.bu.edu/documents/location_web.pdf http://ipsit.bu.edu/documents/jsac_web.pdf
• M. PASTORI. Les codes identifiants ou comment sauver le palais des flammes ? Découverte N°369. juillet-août 2010. p. 56-59
• Abdellah MALLEK, Codes identifiants dans les graphes : Théorie et applications, mémoire de Licence en Recherche Opérationnelle à l'Université des sciences et de la technologie Houari-Boumediene, proposé par M. Ahmed SEMRI, 2011-2012.