Hispanopedia Wiki
Articulo de referencia

Graph center

A graph with central points colored red. These are the three vertices A such that d ( A , B ) ≤ 3 for all vertices B . Each black vertex is a distance of at least 4 fr...

Hispanopedia WikiContenido en espanolLectura gratuita

A graph with central points colored red. These are the three vertices A such that d(A, B) ≤ 3 for all vertices B. Each black vertex is a distance of at least 4 from some other vertex.

The center (or Jordan center[1]) of a graph is the set of all vertices of minimum eccentricity,[2] that is, the set of all vertices u where the greatest distance d(u,v) to other vertices v is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius.[3] Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.

This is also known as the vertex 1-center problem and can be extended to the vertex k-center problem.

Finding the center of a graph is useful in facility location problems where the goal is to minimize the worst-case distance to the facility. For example, placing a hospital at a central point reduces the longest distance the ambulance has to travel.

The center can be found using the Floyd–Warshall algorithm.[4][5] Another algorithm has been proposed based on matrix calculus.[6]

The concept of the center of a graph is related to the closeness centrality measure in social network analysis, which is the reciprocal of the mean of the distances d(A,B).[1]

References

  1. 12Wasserman, Stanley, and Faust, Katherine (1994), Social Network Analysis: Methods and Applications, page 185. Cambridge: Cambridge University Press. ISBN 0-521-38269-6
  2. ↑McHugh, James A., Algorithmic Graph TheoryArchived 2010-08-01 at the Wayback Machine
  3. ↑Weisstein, Eric W."Graph center". MathWorld.
  4. ↑Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
  5. ↑ Warshall, Stephen (enero de 1962). "Un teorema sobre matrices booleanas". Journal of the ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
  6. ↑ "Un nuevo algoritmo para el cálculo del centro de un grafo y la partición de grafos según la distancia al centro" . Octubre de 2019.