El centro (o centro de Jordan [1] ) de un gráfico es el conjunto de todos los vértices de excentricidad mínima , [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ínimo. De manera equivalente, es el conjunto de vértices con excentricidad igual al radio del gráfico . [3] Por lo tanto, los vértices en el centro ( puntos centrales ) minimizan la distancia máxima de otros puntos en el gráfico.
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 a la instalación en el peor de los casos. Por ejemplo, colocar un hospital en un punto central reduce la distancia más larga 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]
Referencias
- ^ a b Wasserman, Stanley y Faust, Katherine (1994), Análisis de redes sociales: métodos y aplicaciones , página 185. Cambridge: Cambridge University Press. ISBN 0-521-38269-6
- ^ McHugh, James A., Teoría de gráficos algorítmicos. Archivado el 1 de agosto de 2010 en la Wayback Machine.
- ^ Weisstein, Eric W. "Centro gráfico" . MathWorld .
- ^ Floyd, Robert W. (junio de 1962). "Algoritmo 97: Ruta más corta". Comunicaciones de la ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
- ^ Warshall, Stephen (enero de 1962). "Un teorema sobre matrices booleanas". Revista de la ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
- ^ https://hal.archives-ouvertes.fr/hal-02304090