Distance (théorie des graphes)

En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds[1]. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie.

Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.