Adjacents (sommets)

Imaginez un plan composé de points et de traits. Deux points sont adjacents lorsqu'un même trait les relie directement. Si plusieurs traits sont nécessaires pour passer de l'un à l'autre, ces points ne sont pas adjacents, même s'il existe un chemin entre eux.

Autour d'un point, tous les points atteignables en un seul trait forment son voisinage. Les compter donne le degré de ce point. L'adjacence décrit donc une relation locale : elle indique qui est voisin immédiat de qui.

Un graphe non orienté est constitué d'un ensemble de sommets, noté V, et d'un ensemble d'arêtes, noté E. Pour deux sommets distincts u et v, l'adjacence signifie qu'une arête a exactement ces deux extrémités : $\{u,v\}\in E\backslash \{u,v\backslash \}\backslash in\; E$. Cette relation est symétrique : si u est adjacent à v, alors v est adjacent à u.

Le voisinage d'un sommet v, noté N(v), rassemble tous ses sommets adjacents. Il s'écrit $N(v)=\{u\in V\mid \{u,v\}\in E\}N(v)=\backslash \{u\backslash in\; V\backslash mid\; \backslash \{u,v\backslash \}\backslash in\; E\backslash \}$. Dans un graphe simple non orienté, le degré de v est le nombre d'éléments de N(v). L'adjacence porte sur une paire de sommets, tandis que le voisinage et le degré sont attachés à un sommet choisi. Ces données locales servent ensuite à étudier des propriétés globales, notamment les chemins, la connexité, les cycles et les colorations. Dans un graphe orienté ou autorisant des boucles, les conventions doivent être précisées, car voisinage et degré peuvent se décliner autrement.

Considérons le graphe non orienté dont les sommets sont A, B, C et D. Ses arêtes sont {A, B}, {A, C}, {B, C} et {C, D}. La figure associée reprend exactement ces données.

1. On choisit le sommet C et on examine seulement les arêtes qui le touchent.

2. Les arêtes {A, C}, {B, C} et {C, D} relient directement C aux sommets A, B et D. Ces trois sommets sont donc adjacents à C.

3. Le voisinage de C est N(C) = {A, B, D}. Il contient trois sommets, donc le degré de C vaut 3.

4. Pour contrôler le résultat, on recompte les arêtes ayant C pour extrémité : il y en a bien trois. L'arête {A, B} ne compte pas pour le degré de C, car elle ne touche pas C.

Sur un réseau routier modélisé par un graphe, deux carrefours sont adjacents lorsqu'un tronçon direct les relie. Pour savoir s'il faut traverser plusieurs carrefours, on recherche plutôt un chemin.

Dans un réseau informatique, le voisinage d'un appareil recense ses liaisons directes. Son degré donne immédiatement le nombre de connexions locales, sans renseigner à lui seul sur tout le réseau.

Pour colorier un graphe, on vérifie chaque arête : ses deux sommets adjacents doivent recevoir des couleurs différentes. Si deux sommets ne sont reliés que par un chemin, cette contrainte ne s'applique pas directement à leur paire.

Adjacence et existence d'un chemin. Deux sommets adjacents sont reliés par au moins une arête. Dans l'exemple, A et D ne sont pas adjacents, même si le chemin A–C–D permet de passer de l'un à l'autre.

Voisinage et degré. Le voisinage est un ensemble de sommets ; le degré est un nombre. Pour C, le voisinage est {A, B, D}, tandis que le degré vaut 3.

Arête et sommets adjacents. L'arête est le lien du graphe ; l'adjacence est la relation qu'elle établit entre ses extrémités. {A, C} est une arête, alors que A et C sont les sommets adjacents correspondants.

Graphe orienté. Une flèche de u vers v ne joue pas le même rôle qu'une arête non orientée. Il faut alors distinguer les voisins sortants des voisins entrants au lieu de supposer l'adjacence symétrique.

Boucles et arêtes multiples. Dans un graphe qui les autorise, compter les voisins ne suffit pas toujours à calculer le degré. Une boucle contribue généralement deux fois au degré dans un graphe non orienté, tandis qu'elle n'ajoute qu'un sommet distinct au voisinage.

Croisement du dessin. Le croisement visuel de deux arêtes n'est pas un sommet s'il n'est pas explicitement marqué. Il ne crée donc aucune nouvelle adjacence ; seules les extrémités déclarées comptent.

Proximité visuelle. Deux sommets dessinés côte à côte ne sont pas forcément adjacents. Inversement, des sommets éloignés sur la page peuvent l'être : on vérifie l'existence d'une arête, jamais la distance dans la représentation.

Le glossaire arête d'un graphe précise la nature du lien qui rend deux sommets adjacents.

La fiche Voisinage développe l'ensemble formé par les voisins immédiats d'un sommet.

La notion de degré d'un sommet d'un graphe explique comment compter les connexions locales.

La fiche coloration d'un graphe montre une application où deux sommets adjacents doivent être distingués.