Rayon (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 Rayon.

En théorie des graphes, le rayon d'un graphe est l'excentricité minimale de ses sommets, c'est-à-dire la plus petite distance à laquelle puisse se trouver un sommet de tous les autres. Le centre d'un graphe est formé de l'ensemble de ses sommets d'excentricité minimale.

L'excentricité maximale est appelée diamètre.

La distance entre deux sommets dans un graphe est définie par la longueur d'un plus court chemin entre ces deux sommets.

Exemples[modifier | modifier le code]