Graphe médian

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

En théorie des graphes, les médianes d'un triplet de sommets ${\displaystyle u,v,w\in G}$ sont les sommets ${\displaystyle z}$ se trouvant sur les plus courts chemins entre ces sommets. Autrement dit, si ${\displaystyle I(u,v)}$, l’intervalle entre ${\displaystyle u}$ et ${\displaystyle v}$, est l'ensemble de sommets sur les plus courts chemins entre ${\displaystyle u}$ et ${\displaystyle v}$, alors l'ensemble des sommets médians est la triple intersection${\displaystyle S_{m}(u,v,w)=\{I(u,v)\cap I(u,w)\cap I(v,w)\}}$. 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 ${\displaystyle |S_{m}(u,v,w)|=1,\forall x,y,z\in G}$.

Propriétés

• Le produit cartésien de deux graphes médians est un graphe médian.
• Le seul graphe médian régulier est l'hypercube.
• Les arbres sont des graphes médians. Alors, par produit cartésien, les grilles sont aussi des graphes médians.

Notes et références

• Portail de l'informatique théorique