Les codes identifiants

Supposons que vous, lecteur, êtes l’administrateur d’un immense réseau de processeur qui tombe souvent en panne à cause de la surchauffe d’un des processeurs. Comment feriez-vous pour trouver quel processeur dysfonctionne de manière optimale (rapide et avec le moins de test possible) ?

C’est en 1998 que, M. Karpovsky, K. Charkrabary et Lev B. Levitin ont répondu à ce problème en abordant dans le cadre de leur recherches le problème de couverture des sommets d’un graphe G de telle façon que l’on peut identifier d’une façon unique n’importe quel sommet de G. Ce fut là la première fois où la notion de codes identifiants a été utilisée.

Comme vous l’aurez compris, ce sujet des Mathématiques Discrètes est assez jeune. Néanmoins, il a su s’imposer comme un très bon moyen de résolution dans bien des domaines tels que la reconnaissance de formes, le séquençage d’ADN, l’aide au diagnostic médical ou encore la communication dans des réseaux multi-utilisateurs.

 Et, malgré son aspect ludique accessible, il suscite bien des interrogations qui pour certaines n’ont toujours pas rencontrés de solutions.

Mais, avant d’aborder ces mystères, commençons par définir quelques notions fondamentales.

Notions de base

Avant de pouvoir aborder les codes identifiants, voyons ensembles des notions fondamentales a son explication :

  •      Les graphes :  Soient V un ensemble (fini ou infini) et E une partie de V ×V (i.e. une relation binaire sur V). Le graphe G = (V, E) est la donnée du couple (V, E) : les éléments de V sont appelés les sommets ou nœuds de G tandis que les éléments de E sont appelés les arcs ou arêtes de G. Si V est un ensemble fini, on parlera alors de graphe fini. Tous les graphes considérés dans la suite de ce travail sont non orientés i.e. E est une relation symétrique sur V.
  • Les voisins : Un sommet u est voisin d’un sommet v s’il existe une arête entre u et v. On dira aussi que u et v sont adjacents. L’ensemble de tous les voisins d’un sommet u est son voisinage, noté N(u). Le degré d’un sommet u est aussi égal au cardinal de N(u). L’ensemble N[u] désigne le voisinage fermé de u, c’est-à-dire N(u)∪{u}.
  • Code couvrant :  Un sous-ensemble de sommets D ⊆ V est un code couvrant (ou dominant) du graphe G si tout sommet de V est couvert par au moins un sommet de D, c'est à dire que pour n'importe quels sommets de V il y a au moins un sommet de D qui est lié à lui.
  •   Sommet séparateur : Deux sommets u et v sont dits séparés par w si celui-ci couvre l’un des sommets u ou v mais pas l’autre. En d’autres termes, u et v sont séparés par w si w appartient à N[u](delta)N[v], la différence symétrique de N[u] et N[v].
Prenons ce graphe en exemple: le sommet 4 est un sommet séparateur du sommet 5 et du sommet 1, le sommet 2 est un sommet séparateur des sommets 3 et 4, le sommet 6 est séparateur des sommets 4 et 3, etc....
  •   Code séparateur : Un sous-ensemble S ⊆ V est un code séparant du graphe G si deux sommets distincts de V sont séparés par au moins un sommet de S, c'est à dire que, pour deux sommets u,v appartenant à V et w appartenant à S, w est un sommet séparateur de u et v.

Maintenant que vous avez compris tout ça, vous savez qu’est-ce qu’un code identifiant ! Quoi, vous ne nous croyez pas, mais si laissez nous vous expliquer.

Le code identifiant

Un code identifiant est un ensemble de sommets (que nous appellerons dorénavant C) du graphe G qui va nous permettre d’identifier tous les sommets de ce dernier par les sommets de C présent dans leur voisinage fermé.

Alors, vous n’êtes toujours pas convaincu que vous maîtrisez la notion de code identifiant ! En voici l’explication ultime : Le code identifiant d’un graphe et en fait l’union de son code couvrant et de son code séparateur.

Et oui, notre ensemble C est couvrant car il doit atteindre tous les sommets du graphes ET séparateur car il caractérise chacun des sommets du graphes.

Mais attention, n’est pas un graphe propriétaire d’un code identifiant qui le veut !

En effet, un graphe contenant deux sommets u et v tel que N(u) = N(v) n’aura pas de code identifiant car il n’existe aucun moyen de les différencier. Prenons un exemple plutôt, disons que vous avez une propriété ressemblant à ceci (voir fig.1),

Et que vous vouliez y mettre des alarmes incendies. Mais vous ne voulez pas équiper toutes les pièces d’alarmes (faute de budget, disons que vous avez hérité de la propriété). Le meilleur moyen de trouver une solution serait de créer un graphe avec les sommets représentant les pièces et les arcs les portes liants 2 pièces, et de définir le code identifiant de ce graphe qui représentera les salles équipées d’alarmes.

En faisant cela (voir Fig.2), nous remarquons que plusieurs sommets ont les mêmes voisins, du coup il nous est impossible de définir un code identifiant valable. (les sommets en jaunes sont les sommets identifiants)

Pour être plus précis, imaginons que, pour le sous graphe composé des sommets A, B, C et D, nous ayons des détecteurs de fumées dans les pièces B et D.

Si un feu s’allume en A, les détecteurs des salles B et D s’activeront.

Si un feu s’allume en C, les détecteurs des salles B et D s’activeront.

Nous ne pouvons donc pas différencier les salles A et C lors d’un incendie et, par extension, ne pouvant pas les identifier avec un code identifiant.

Mais alors, dans quel cas un code identifiant marcherait-il me diriez-vous ?

Prenons encore une fois l’exemple d’une maison qui prend feu, cette fois avec un configuration propice à l’utilisation des codes identifiants pour placer les détecteurs de fumées.

Dans ce cas, lorsqu’une pièce prendra feu, et malgré le fait qu’il n’y ai pas de détecteur de fumées dans chaque pièce, nous pourrions déterminer la pièce qui prendra feu grâce aux différents signaux renvoyés par les détecteurs. Pour être plus précis, voici un exemple des signaux renvoyés par chacune des pièces équipées d'alarmes incendies pour n'importe quelles pièces de la maison qui prendraient feu.

1 = {2} ;

2 = {2,3,6,5} ;

3 = {2,3} ;

4 = {3,5} ;

5 = {6,5,2}

6 = {2,5,7,6}

7 = {6,5,7}

8 = {7}

9 = {6}

Donc si par exemple on reçoit un message des détecteurs des salles 3 et 5, on sait qu’un feu a démarré dans la salle 4, étant donné que la salle 2 n'a rien détecté.

Autres utilisations

Les maisons en feu ne sont pas les seuls cas pratiques des codes identifiant, en voici quelques autres :

•On dispose d’un nombre important d’antennes satellites, et on recherche à détecter un phénomène grâce à ces antennes.  Comment savoir avec certitude et rapidement que l’antenne à repérer le phénomène ? Ces deux situations peuvent se résoudre en modélisant la situation par une recherche d’un code identifiant dans un graphe.

• Le Qui est-ce ? est un très bon exemple de cas pratique du code identifiant. En utilisant le code identifiant, nous pouvons déduire façon de jouer que l’on nommera « Méthode adaptative ». Cette méthode a pour but de ne poser que les questions liées au maximum de joueurs dans le but d’être le plus efficace. Nous pouvons assimiler ses questions a des sommets de code identifiant. En posant les bonnes questions, il nous est possible de sélectionner efficacement le bon personnage.

Et en comparant à une méthode naïve qui serait de poser des questions aléatoirement, on voit que dans la 95% des cas la méthode adaptative est plus efficace.

http://jdoodle.com/a/1LkF

(Pour lancer le test, aller sur le site est appuyer sur exécuter. Vous verrez que dans la majorité des cas, c'est la méthode adaptative qui l'emporte sur la méthode naïve)

1 Cliquer pour recommander cet article