Codes identifiants d’un graphe et ses applications

Pour respecter les normes de sécurité, une Université doit installer des alarmes incendies pour prévenir des feux. Or, ces alarmes ont un coût, l'Université cherche donc à minimiser ses dépences tout en gardant une couverture maximale.

Ces alarmes peuvent détecter un feu dans la pièce dans laquelle elle sont installées et les pièces adjacentes. L'idée est donc de trouver l'agencement optimale de ces alarmes pour limiter le coût d'installation tout en gardant un établissement sécurisé.

En Mathématiques, cette recherche s'appelle la recherche de Code Identifiant.
L'idée ici va être d'installer les alarmes incendies de sorte qu'à leur interrogation, on pourra toujours affirmer de source sûre, s'il y a un incendie ou non dans le bâtiment et si oui, dans quelle pièce exactement. Evidemment, il n'y aura pas toujours besoin d'interroger toutes les alarmes.
Voyons un exemple pour illustrer ça et ainsi être dans de bonnes dispositions pour la suite

Exemple de la détection d'un incendie dans un bâtiment.

Nous avons ici la représentation d'un bâtiment. Chaque sommet (A, B, C, D, etc...) désigne une pièce et chaque arête (trait liant deux sommets) une porte entre les pièces. Nous avons donc par exemple B qui est une pièce voisine de A, mais C qui n'est pas voisine de A.

Nous voyons que les sommets violets et roses répondent "oui" lorsqu'ils sont interrogés, ce qui veut dire qu'il y a un incendie dans le bâtiment et nous avons comme possibilités A et C puisqu'ils sont tous deux voisins de ces sommets. Hors nous voyons que le sommet vert répond "non". Cela veut dire qu'il n'y a pas d'incendie dans la pièce du sommet vert et toutes ses pièces adjacentes. C étant voisin du sommet vert, Il n'est pas en feu.
On peut donc affirmer que le sommet en feu est A.

Maintenant que nous avons compris comment cela fonctionne, nous pouvons passer à la théorie mathématique !

10 Cliquer pour recommander cet article