Codes Identifiants

Figure 4

Plan 

1. Introduction.

2. Problématique.

3. Définitions.

3.1.  Code identifiant d’un graphe.

3.2.  Généralités sur les codes identifiants.

3.2.1  Codes couvrants.

3.2.2 Codes séparateurs.

4. Plan de l’université, et le graphe qui le modélise.

5.  Algorithmes.

5.1. Le premier algorithme.

5.2. Le deuxième algorithme (suite)

6. Problèmes rencontrés.

7. Exercice

Bibliographie.

1.  Introduction

      Dans le cadre de ce premier projet en mathématiques discrètes, nous nous   intéresserons à la création d’une solution permettant de détecter un incendie dans un établissement universitaire, et ce avec le moins de détecteurs à fumée installés dans les pièces.

         Il s’agit donc de la création d’un algorithme performant, capable à l’aide d’un schéma graphique de déduire le nombre minimal de détecteurs à installer dans certaines pièces, et ce afin de diminuer l’achat de ces appareils tout en garantissant une sécurité optimale face aux flammes.

A la fin , un exercice sera proposé afin de mieux comprendre les solutions possible ( ou non ) pour le problème traité .

2.  Problématique

       Aujourd'hui et plus que jamais, les incidents liés à des incendies dans nos lieux publics se multiplient. Cependant ; malgré l'existence de méthodes permettant un accroissement de la sécurité non négligeable, leurs coups eux; restent assez importants surtout lorsqu’il s’agit de localiser précisément les flammes dès leurs apparitions dans une pièce spécifique, et ce car l’organisation d’un très grand nombre de détecteurs de fumer dans une université ou autres se révèle être une tâche très difficile. C’est donc en réaction à cette problématique que nous apportons une solution permettant avec le minimum d'appareils installés, de localiser à temps l’apparition d’un feu dans une pièce dans laquelle il se trouve ou dans les pièces adjacentes, et ce de manière totalement automatique.

         En mathématiques, la méthode pour retrouver la pièce en flammes parmi les autres pièces utilise le principe des codes identifiants.

3. Définitions

3.1. Code identifiant d’un graphe

        “En mathématiques, et plus précisément en théorie des graphes, un code identifiant d’un graphe est un sous-ensemble de ses sommets tels que chaque sommet du graphe est identifié de façon unique par l’ensemble de ses voisins dans le code. Un sous-ensemble 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.” [1]

3.2. Généralité sur les codes identifiants    

3.2.1  Codes couvrants

     “ Soit 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 :              

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

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

3.2.2 Codes séparateurs

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

     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. ”  [2]

4.  Plan de l’université, et le graphe qui le modélise

La figure 1  représente un plan fictif d’une université avant l'installation des détecteurs de fumées.                                     

La figure 2 représente à la fois le plan d’une université (celui vu précédemment dans la figure 1) mais aussi un graphe, pour lequel chaque nœud représente une salle, et chaque arête représente deux sales reliées par une porte.

La figure 3 ci-dessous représente le même graphe vu précédemment (figure 2) sans le plan des salle superposé sur lui, avec les nœuds ayant chacun une lettre de l’alphabet afin de les identifier de manière unique.

5. Algorithmes

Afin de résoudre la problématique de la mise en place à coûts minimums des détecteurs de fumée, notamment dans l’exemple vu précédemment (figures 1,2,3), nous avons élaborés les deux algorithmes ci-dessous :

5.1 Le premier algorithme

L’algorithme ci-dessous a pour principale fonction de trouver une couverture minimale, et donc de trouver le code couvrant aux graphes représentant les salles et portes d’un l’établissement donné, et ce afin de détecter une éventuelle apparition de flemme avec le moins d’appareils installés (le système couvre toute les salles)..

G (S,A);

Tantque (il existe un sommet non découvre)

    pour chaque s dans S

     faire

           si s.couleur == blanc alors N=1;

           sinon N=0;

           fsi;

           pour chaque (s,u) dans A

            faire

                     si u.couleur == blanc alors N=N+1;

                     fsi;

            fait;

           P=socket(s,N);

     fait;

    s=Nmax(P);

    s.couleur=noir;

    pour chaque (s,u) dans A

     faire

           u.couleur = gris;

     fait;

fin;

●  Explication

L’algorithme vu précédemment consiste à mettre un nœuds en :

-        Couleur blanche si le sommet est non découvert.

-        Couleur grise si le sommet est découvert.

-        Couleur noire si le sommet dispose d’un détecteur de fumée   .

G(S,A) => S ensemble de sommets

                A ensemble d'arêtes.

Fonction Socket(s,N) => stocke dans une structure de données le sommet 's' avec le nombre de ses voisins non découvres 'N'.

Fonction Nmax(P) => renvoi un sommet 's' avec le max de nombre de voisins non découvres 'N'.

●   Principe

-        Étape 1 :  l’algorithme va vérifier à chaque foi et pour chaque sommet son nombre de sommet adjacent non découvert et calculer ainsi son degré grâce  la variable N.

-        Étape 2 : puis il recherchera le sommet ayant le degré maximum dans le graphe qui ne dispose pas de détecteurs de fumée

-        Étape 3 : enfin il répétera à partir de l’opération jusqu'à ne plus avoir de sommets non découverts (blanc) dans le graphe, ainsi il garantira la couverture en cas d’incendie

●   Exemple et Exécution

Après exécution de l’algorithme sur l'exemple traité dans les figures 1,2,3 nous avons obtenu l’ensemble {H,B,F,K} pour les nœuds/salles disposant d’un détecteur de fumées.

Notons que cette algorithme ne permet que la détection et non la localisation d’un feu.

5.2 Le deuxième algorithme (suite)

L’algorithme ci-dessous a pour but de localiser une flemme dans une pièce en utilisant la combinaison des radars adjacents à celle-ci qu’il lui est propre.

Début

pour chaque s dans S

faire

     si s.couleur == noire alors P(s)=Ajouter(s);  fsi;

      pour chaque (s,u) dans A

      faire

          si u.couleur == noire alors P(s)=Ajouter(u);  fsi;

      fait;

fait;

Tantque ( non séparé(P) )

faire

     pour chaque P(i)

     faire

        pour chaque p(j) et p(i) == p(j)

          faire

             si( ( i ) non voisins de ( j ) ) alors V=ajout(i); v=ajout(j); 

             fsi;

 pour chaque u (dans voisins de i et non dans voisins de j) ou (dans voisins           de j et non dans voisins de i )

               faire

                  V=ajout(u);

              fait;

          fait;    

    fait;

fait;

s= Maxapparence(V);

s.couleur = noire;

fin;

●   Explication

{ fonction P(s) = Ajouter(u) } => ajoute un élément 'u' dans une structure de données ou l'indice est le sommet 's'. }

{ fonction séparé(P) } vérifie si dans une structure de données P que pour chaque un indice leur valeur est différents. }

{ fonction v=ajout(i) } => ajoute un sommet i dans un tableau v . . }

{ fonctions=Maxapparence(V)}=>renvoi un sommet s  qui a le nombre d'apparence max dans le tableau V }

●   Principe

-        Étape 1 : pour chaque nœud du graphe on lui associe une séquence spécifique de nœuds disposant d’un détecteur (structure P(x) ), ainsi en cas d’incendie il suffira de comparer la séquence détectée avec celle déjà présente dans le système, et ainsi il pourra aisément localiser l’incendie.

-        Étape 2 : l’algorithme va après l'insertion des séquences vérifier s’il existe une séquence similaire pour un autre nœud, si tel est le cas il ajoutera à l’une de ces séquences un nœud ne figurant dans aucun des deux nœuds évoqués et n’ayant pas encore de détecteur. Le système va ajouter ce dit nœud, à la liste des nœuds disposant d’un détecteur de fumée (il va le colorier en noir).

●  Exemple et exécution

Toujours après exécution de l’algorithme sur l'exemple traité dans les figures 1,2,3 nous avons obtenu l’ensemble {H,B,F,K,D,J} pour les nœuds/salles disposant d’un détecteur de fumée, ainsi le système est en mesure de localiser un incendie dans n’importe quelle pièce avec le minimum de détecteurs installés.

En utilisant la méthode de Qui-est-ce nous pouvons déduire le tableau de la figure 4

6. Problème rencontrés

Parmi les problèmes rencontré lors de la phase de conception du système nous avons déduit que : [3]

-        Il est impossible de détecter un incendie sur un graphe complet, et ce pour n’importe quel algorithme, car les séquence de nœuds munis d'un détecteur permettant sa détection sont les mêmes pour tous les nœuds.

-        Il est possible d’avoir plusieurs solutions ayant des complexités différentes si dans un certain cas nous nous retrouvons avec un problème très fréquent dans les Vertex Cover, où avec plusieurs nœuds de même degré maximum il sera possible selon le premier nœud choisit; d’avoir une organisation des détecteurs totalement différente.

7. Exercice

1 : a) -  Peut on toujours trouver une solution au problème de base ( installation des détecteurs de fumés )  ?

b) - Est-ce qu'il y a une solutions quand toutes les salles sont adjacents ?

2 :  a) - Est-ce que l'algorithme donnée précédemment trouvera toujours la solution la plus optimale quelque soit le cas traité par celui ci ?                

b) Si non , justifiez votre réponse par un contre exemple

Bibliographie

[1]
«Wikipeida,» 2019. [En ligne]. Available: https://fr.wikipedia.org/wiki/Code_identifiant_d%27un_graphe.
[2]
M. Vandermeer, «matheo.uliege,» 2017. [En ligne]. Available: https://matheo.uliege.be/bitstream/2268.2/5008/4/Memoire_MarionVandermeer_s122634.pdf.
[3]
R. Campigotto, «tel archives,» 12 2011. [En ligne]. Available: https://tel.archives-ouvertes.fr/tel-00677774/document. 

0 Cliquer pour recommander cet article