Voisinage (théorie des graphes)

En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête. Le voisinage d'un sommet peut désigner l'ensemble de ses sommets voisins ou bien un sous-graphe associé, par exemple le sous-graphe induit. Dans un graphe orienté, on emploie généralement le terme de prédécesseur ou de successeur.

Définition formelle

Définition classique

Dans un graphe non orienté ${\displaystyle G=(V,E)}$, le voisinage d'un sommet ${\displaystyle v\in V}$, souvent noté ${\displaystyle N_{G}(v)}$ (N pour neighbourhood) peut désigner plusieurs choses :

• L'ensemble des sommets voisins : ${\displaystyle \{w:(v,w)\in E\}}$[1]
• Le sous-graphe de ${\displaystyle G}$ induit par les sommets précédents, avec ou sans ${\displaystyle v}$ selon les versions.

Variantes

• Dans le cas des graphes orientés, on peut aussi définir une notion de voisinage orienté.
• Il arrive que l'on considère le voisinage à distance ${\displaystyle k}$ d'un sommet, c'est-à-dire tous les sommets séparés de v par moins de k arêtes. C'est le cas notamment en calcul distribué synchrone[2].

Utilisations

La notion de voisinage est une notion classique de théorie des graphes, elle intervient par exemple pour définir les concepts de coloration, de stabilité et de couverture par sommets.

Un exemple d'application est la modélisation des réseaux sociaux où le voisinage d'un sommet représente les connaissances d'une personne. Dans ce cadre le voisinage permet de définir le coefficient de clustering.

Notes et références

1. Par exemple dans Olivier Fouquet, Théorie des graphes : une brève introduction (avec un biais algébrique assumé), 2012 (lire en ligne [PDF]).
2. Voir par exemple David Peleg, Distributed Computing : A Locality-Sensitive Approach, vol. 5, SIAM, 2000