Aller au contenu

Graphe médian

Un article de Wikipédia, l'encyclopédie libre.

En théorie des graphes, un graphe médian est un type de graphe. Étant donné un triplet de nœuds dans un graphe, les médianes de ces sommets sont les sommets se trouvant sur les plus courts chemins entre les paires de sommets. Un graphe médian est un graphe tel que pour tout triplet de nœuds il existe un unique sommet qui soit une médiane.

Définitions

[modifier | modifier le code]

En théorie des graphes, les médianes d'un triplet de sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets[1]. Autrement dit, si , l’intervalle entre et , est l'ensemble de sommets sur les plus courts chemins entre et , alors l'ensemble des sommets médians est la triple intersection. Un graphe médian est un graphe tel que tout triplet de sommets, qu'il y a une seule et unique médiane, 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).