Codes identifiants d’un graphe et ses applications

Application pour la détection d'un feu

Résolution du problème

Maintenant que l'on a pu voir comment fonctionne les codes identifiants et comment les utiliser dans des scénarios de la vie de tous les jours, on peut maintenant comprendre comment résoudre le problème décrit au début de notre blog.

Si on souhaite minimiser le nombre d'alarmes incendies installées dans une université, il nous suffit de modéliser notre université, comme un ensemble de salles reliées entre-elles.

Exemple de graphe reliant différentes salles

Nous relions une salle à chaque salle adjacente à celle-ci, il nous suffira alors de déterminer un code identifiant C de celui-ci et mettre en place des alarmes incendies dans chaque salle présente dans mon sous-ensemble C.

Ici, notre code identifiant correspondra aux alarmes incendies installées de façon optimale dans le batîment.

Voici le déroulement d'un algorithme adaptatif dans un tel cas :

Comme on a pu le voir, dès qu'un sommet renvoie vrai, on vérifie ses voisins et dès que l'on a un sous-ensemble d'un seul sommet, nous sommes capables d'affirmer que c'est ce tel sommet qui est en feu.

Pour aller plus loin

Ici, nous nous sommes attaqués à des cas de graphes simples pour la détection de code identifiant.
Mais parfois, il peut être plus compliqué de les modéliser, nous avons eu un petit exemple avec le cas du Qui-est-ce?

Voici divers sources si vous souhaitez en connaître d'avantages sur les codes identifiants :

D'autres exemples de code identifiant :
https://www.researchgate.net/publication/225702395_Optimal_Identifying_Codes_in_Cycles_and_Paths

Pour mieux comprendre la difficulté dans la détermination d'une complexité pour les codes identifiants :
http://cedric.cnam.fr/~bentzc/INITREC/Files/OH1.pdf

TER d'un élève de l'ENSIMAG sur les codes identifiants et leur application dans des Hypercubes ( Utilisé pour les machines effectuant des calculs parallèles ) :
https://ensiwiki.ensimag.fr/images/b/b9/TER0910_rapport_LehouillierThibault.pdf

Bibliographie :


Illustration des exemples tirés de la thèse de Marion Vandermeer à l'université de liège.
Illustration de graphes et inspiration : http://www.palais-decouverte.fr/fileadmin/fileadmin_Palais/fichiersContribs/au-programme/expos-permanentes/mathematiques/Formes/pdf_revue/369_juil_aout_2k10.pdf
Inspiration pour la modélisation du jeu "Qui est-ce ?" :
https://perso.liris.cnrs.fr/aline.parreau/Research/Slides/seminaireENS.pdf
Idée de la modélisation pour un réseau multiprocesseurs :
http://people.ee.duke.edu/~krish/00661507.pdf
Sources des définitions :
Wiki de Ensimag - Grenoble
Wikipédia

11 Cliquer pour recommander cet article