diamètre d’un graphe

diamètre d’un graphe

Plus longue distance entre deux sommets d’un graphe connexe.

Le diamètre d’un graphe est, autrement dit, le plus grand nombre d’arêtes, dans un graphe non orienté ou d’arcs dans un graphe orienté, qu’on peut trouver entre deux sommets distincts de ce graphe.

Exemple

Le diamètre du graphe ci-dessous est 4.  En effet, la plus grande distance entre les sommets A et E est donnée par la longueur de la chaîne A – B – C – D – E.