Diamètre (théorie des graphes)
En théorie des graphes, le diamètre d'un graphe est la plus grande distance possible qui puisse exister entre deux de ses sommets ; la distance entre deux sommets étant définie par la longueur d'un plus court chemin entre ces deux sommets[1].
En d'autres termes, le diamètre est l'excentricité maximale de ses sommets. L'excentricité minimale est appelée rayon.
Exemples
-
Le Graphe taureau a un diamètre de 3. Les deux sommets les plus éloignés sont les deux extrémités des cornes.
-
Le graphe de Coxeter a un diamètre de 4.
-
Le Snark de Szekeres a un diamètre de 7.
Notes et références
- ↑ (en) Eric W. Weisstein, « Graph Diameter », sur mathworld.wolfram.com (consulté le )
- Portail de l'informatique théorique
- Portail des mathématiques