Quelle est la différence entre un arc et une arête dans un graphe ?

Réponse courte

Une arête relie deux sommets dans un graphe non orienté et n’a pas de sens de parcours privilégié. Un arc relie un sommet de départ à un sommet d’arrivée dans un graphe orienté.

Comprendre

Lien sans sens ou lien orienté

Un graphe représente des sommets et des relations entre eux. Dans un graphe non orienté, une arête entre A et B exprime une relation réciproque : elle permet de considérer A relié à B comme B relié à A. Dans un graphe orienté, un arc porte un sens, de son origine vers son extrémité. La présence de l’arc A vers B ne garantit pas celle de l’arc B vers A.

Lire une situation

Pour modéliser des routes à double sens entre deux villes, on peut utiliser une arête non orientée. Pour des rues à sens unique, un arc va de la ville où l’on entre vers celle où l’on peut sortir. De même, si un compte suit une autre personne sur un réseau modélisé, la relation « suit » peut être représentée par un arc orienté : suivre A ne signifie pas forcément qu’A suit aussi ce compte.

Conséquence sur le voisinage

Dans un graphe orienté, on distingue les arcs sortants d’un sommet et les arcs entrants. Un arc A→B fait de B un successeur de A, et de A un prédécesseur de B. Dans un graphe non orienté, les deux extrémités sont voisines sans distinction de départ et d’arrivée. Ne déduis pas le sens d’un lien de la façon dont la figure est dessinée : il faut lire la flèche ou la définition du graphe.

Exemples

  • Dans un graphe non orienté, l’arête {A, B} relie A à B et B à A.
  • Dans un graphe orienté ayant l’arc A→B sans B→A, on peut aller de A vers B, mais pas conclure qu’on peut revenir par un arc.

Pièges fréquents

  • Supposer qu’un arc implique automatiquement l’arc inverse : le sens opposé doit être présent séparément.
  • Appeler arête tout lien dessiné : un graphe orienté utilise des arcs munis d’un sens, souvent indiqué par une flèche.

Et maintenant ?

Questions proches

← Toutes les questions-réponses