Distance (théorie des graphes)
Pour les articles homonymes, voir Distance.
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.
Notes et références[modifier | modifier le code]
- Christophe ROSSIGNOL, « Généralités sur les graphes », sur Académie de Grenoble, .
