El centro (o centro de Jordan [1] ) de un grafo es el conjunto de todos los vértices de mínima excentricidad , [2] es decir, el conjunto de todos los vértices u donde la mayor distancia d ( u , v ) a otros vértices v es mínima. Equivalentemente, es el conjunto de vértices con excentricidad igual al radio del grafo . [3] Por lo tanto, los vértices en el centro ( puntos centrales ) minimizan la distancia máxima desde otros puntos del grafo.
Esto también se conoce como el problema del vértice 1-centro y puede extenderse al problema del vértice k-centro .
Encontrar el centro de un gráfico es útil en problemas de ubicación de instalaciones donde el objetivo es minimizar la distancia en el peor de los casos hasta la instalación. Por ejemplo, ubicar un hospital en un punto central reduce la distancia máxima que debe recorrer la ambulancia.
El centro se puede encontrar utilizando el algoritmo Floyd-Warshall . [4] [5] Se ha propuesto otro algoritmo basado en el cálculo matricial. [6]
El concepto de centro de un gráfico está relacionado con la medida de centralidad de cercanía en el análisis de redes sociales , que es el recíproco de la media de las distancias d ( A , B ). [1]