Grafo mediano

En matemática, y más específicamente en la teoría de grafos, un grafo mediano es un grafo no dirigido en que cualesquiera tres vértices a, b, y c tienen un único mediano. Un mediano es un vértice m(a,b,c) que pertenece a los caminos más cortos entre cualquier par de nodos conformado por a, b, y c.El concepto de grafo mediano ha sido largamente estudiado, por ejemplo, por Birkhoff y Kiss (1947) o (más explícitamente) por Avann (1961), pero el primer artículo en llamarlos ""grafos medianos"" aparece en Nebesk'y (1971). Chung, Graham, y Saks escriben:""Los grafos medianos surgen naturalmente del estudio de los conjuntos ordenados y de los retículos distributivos discretos, y poseen una extensa literatura.""En filogenia, el grafo de Buneman que representa todos los árboles filogenéticos de máxima parsimonia es un grafo mediano. Los grafos medianos también aparecen en la teoría de elección social: si un conjunto de alternativas tiene una estructura de un grafo mediano, es posible derivar una elección no ambigua de las mejores preferencias posibles entre ellas.En Klavžar y Mulder (1999), Bandelt y Chepoi (2008) y Knuth (2008) se presentan ""Surveys"" (artículos científicos que presentan estados del arte sobre un tópico determinado) acerca de grafos medianos.