Codes identifiants d’un graphe et ses applications

Définition d'un code identifiant

Pour comprendre cette notion, il faut définir les graphes. Un graphe G est une paire (S, A) où :
- S est un ensemble dont les éléments sont appelés sommets.
- A est un ensemble de paires de sommets distincts, appelés arêtes.

Exemple d'un graphe

Pour bien comprendre ce qu'est un code identifiant, il nous est nécessaire de faire intervenir deux autres définitions. La définition du code couvrant et du code séparateur.

Supposons un graphe G = (S,A) et C un sous-ensemble du graphe G.

C est un code couvrant de G si tout sommet v de G est voisin d'au moins un sommet de C
Ici, le sous-ensemble contenant les sommets rouges est un code couvrant.
Le voisinage d'un sommet est noté : N(v) (pour Neighbourhood).
Le voisinage étendu Nt est égal à : N(v) U V

C' est un code séparateur de G si pour toutes arêtes (u,v) appartenant à A et u différent de v : 
Nt(u) ∩ C' est différent de N(v) ∩ C'
Ici, il y a bien au moins un sommet rouge entre chaque sommet de S, non inclus dans C'
On peut maintenant définir un code identifiant:

Un sous-ensemble C est un code identifiant d'un graphe G si et seulement si C est un code séparateur et un code couvrant de G.

On peut voir que chaque sommet de S non inclus dans C possède au moins un voisin dans C (Donc les sommets C,B,G sont bien voisins d'un sommet du sous-ensemble C) et qu'ils sont également tous séparés par au moins un sommet de C.
Ce sous-ensemble est donc bien un code séparateur et un code couvrant. Il est donc bien par définition un code identifiant.

10 Cliquer pour recommander cet article