Graphe médian

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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).