Terminale · Numérique et sciences informatiques

Utiliser la relation d'adjacence d'un graphe pour modéliser un réseau et le parcourir

Exploiter la relation entre sommets (adjacence, voisinage) d'un graphe pour modéliser un réseau, puis dérouler un parcours en largeur ou en profondeur en listant les voisins à chaque étape.

Aperçu gratuit
Illustration de la fiche « Utiliser la relation d'adjacence d'un graphe pour modéliser un réseau et le parcourir »

Les points essentiels

  • Un graphe G = (S, A) est défini par un ensemble de sommets S et un ensemble d'arêtes (ou d'arcs) A : chaque élément de A exprime une relation entre deux sommets.
  • Deux sommets sont adjacents (ou voisins) lorsqu'une arête les relie ; dans un graphe non orienté la relation est symétrique, dans un graphe orienté elle ne l'est pas forcément (un arc u→v n'implique pas v→u).

Les mots à connaître

Voisins (adjacence)
Dans un graphe non orienté, les voisins d'un sommet s sont les sommets reliés à s par une arête. Dans un graphe orienté, on distingue les successeurs (arcs sortants) et les prédécesseurs (arcs entrants).
Liste d'adjacence
Représentation d'un graphe où, à chaque sommet, on associe la liste de ses voisins, par exemple en Python un dictionnaire {sommet: [voisins]}.

Un exemple pour comprendre

Un petit réseau social compte cinq personnes A, B, C, D, E. Les relations d'amitié (symétriques) sont : A-B, A-C, B-D, C-D. E n'a aucun ami dans le réseau. Donner la liste d'adjacence, puis dire quels sommets sont atteignables depuis A.

Chaque amitié est une arête non orientée. Listes d'adjacence : A : [B, C] ; B : [A, D] ; C : [A, D] ; D : [B, C] ; E : []. On vérifie la symétrie : A-B apparaît dans la liste de A et dans celle de B, etc. Depuis A, on atteint B et C (voisins de A), puis D (voisin de B et de C). E n'a aucun voisin et aucune arête ne mène à lui : il n'est pas atteignable. Les sommets atteignables sont donc A, B, C, D ; le graphe n'est pas connexe, il a deux composantes connexes : {A, B, C, D} et {E}.

Première page de l’Essentiel : Utiliser la relation d'adjacence d'un graphe pour modéliser un réseau et le parcourir
Ketty