Comment trouver la distance entre deux personnes dans un graphe ?

Réponse courte

Dans un graphe, la distance entre deux sommets est le nombre d’arêtes du plus court chemin qui les relie. Repère tous les chemins possibles entre les deux, puis compte les liens dans le plus court.

Comprendre

Chercher des chemins

Commence par repérer les sommets de départ et d’arrivée, puis trace les chemins qui les relient. La distance correspond au plus petit nombre d’arêtes, c’est-à-dire de liens parcourus. On ne compte pas le nombre de sommets dessinés ni les détours plus longs.

Compter le plus court

Supposons que les seules relations soient A–B, A–C, C–D et D–E. Le chemin A–C–D–E contient trois arêtes : c’est le seul chemin de A à E dans ce graphe, donc la distance entre ces sommets est 3. Le trajet A–B ne permet pas de continuer vers C, car l’arête B–C n’existe pas. On compare uniquement des chemins formés de liens effectivement présents.

Vérifier le modèle

La distance est définie à partir des liens que le graphe représente. Si le réseau est orienté, un lien suivi dans le mauvais sens ne permet pas nécessairement d’avancer. Si aucun chemin ne relie les deux sommets, ils n’ont pas de distance finie dans ce modèle. Dans les exercices, précise si les liens sont orientés et vérifie qu’un raccourci n’a pas été oublié avant de donner le résultat.

Étapes

  1. Repère les deux sommets à relier et le sens autorisé des arêtes.
  2. Énumère ou repère les chemins possibles entre eux.
  3. Compte les arêtes de chaque chemin, sans compter les sommets.
  4. Retient le plus petit compte ; indique qu’aucun chemin n’existe s’ils sont séparés.

Exemples

  • Si A est directement relié à C, leur distance est 1, même si un détour passe par A–B–C.
  • Pour le chemin A–C–D–F, la distance de A à F vaut 3 si aucun chemin plus court n’existe.
  • A–B–C–D–E–F contient cinq arêtes ; si A–C–D–F en contient trois, le second chemin fixe la distance entre A et F.

Pièges fréquents

  • Compter les sommets au lieu des arêtes : un chemin qui passe par quatre sommets successifs contient trois liens.
  • Choisir un chemin visible sans vérifier s’il existe un raccourci : seule la longueur minimale définit la distance.

Et maintenant ?

Questions proches

← Toutes les questions-réponses

Ketty