Distance (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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. C'est une distance au sens mathématique.

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]

  1. Christophe ROSSIGNOL, « Généralités sur les graphes », sur Académie de Grenoble, .