Graphe médian

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, les médians d'un triplet de sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets[1]. Autrement dit, si est l'ensemble de sommets sur les plus courts chemins entre et , alors l'ensemble des sommets médians est . Un graphe médian respecte la propriété qu'il n'y a qu'un seul sommet médian pour tout triplet de sommets, c'est-à-dire .

Propriétés[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a et b (en) Wilfriend Imrich et Sandi Klavzar - Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, (ISBN 0471370398).