Distancia (teoría de grafos)

La "distancia geodésica" vuelve a dirigir aquí. Para conocer las distancias en la superficie de una esfera, consulte Distancia de círculo máximo . Para conocer las distancias en la superficie de la Tierra, consulte Geodésicas en un elipsoide . Para geodésicas en geometría diferencial, consulte Geodésica .

En el campo matemático de la teoría de grafos , la distancia entre dos vértices en un grafo es el número de aristas en un camino más corto (también llamado grafo geodésico ) que los conecta. Esto también se conoce como distancia geodésica . ^[1] Observe que puede haber más de un camino más corto entre dos vértices. ^[2] Si no hay una ruta que conecte los dos vértices, es decir, si pertenecen a diferentes componentes conectados , entonces convencionalmente la distancia se define como infinita.

En el caso de un gráfico dirigido, la distancia entre dos vértices y se define como la longitud de una ruta dirigida más corta de a que consta de arcos, siempre que exista al menos una de tales rutas. ^[3] Nótese que, a diferencia del caso de los gráficos no dirigidos, no necesariamente coincide con , y podría darse el caso de que uno esté definido y el otro no.${\displaystyle d(u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)}$${\displaystyle d(v,u)}$

Conceptos relacionados

Un espacio métrico definido sobre un conjunto de puntos en términos de distancias en un gráfico definido sobre el conjunto se denomina métrica de gráfico . El conjunto de vértices (de un gráfico no dirigido) y la función de distancia forman un espacio métrico, si y solo si el gráfico está conectado .

La excentricidad de un vértice es la mayor distancia entre cualquier otro vértice; en símbolos que es . Se puede pensar en qué tan lejos está un nodo del nodo más distante de él en el gráfico.${\displaystyle \epsilon (v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u)}$

El radio de un gráfico es la excentricidad mínima de cualquier vértice o, en símbolos, .${\displaystyle r}$${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)}$

El diámetro de un gráfico es la excentricidad máxima de cualquier vértice del gráfico. Esto es, es la mayor distancia entre cualquier par de vértices o, alternativamente, . Para encontrar el diámetro de un gráfico, primero encuentre el camino más corto entre cada par de vértices . La mayor longitud de cualquiera de estos caminos es el diámetro del gráfico. ${\displaystyle d}$${\displaystyle d}$${\displaystyle d=\max _{v\in V}\epsilon (v)}$

Un vértice central en una gráfica de radio es aquel cuya excentricidad es , es decir, un vértice que alcanza el radio o, equivalentemente, un vértice tal que .${\displaystyle r}$${\displaystyle r}$${\displaystyle v}$${\displaystyle \epsilon (v)=r}$

Un vértice periférico en una gráfica de diámetro es uno que está a distancia de algún otro vértice, es decir, un vértice que alcanza el diámetro. Formalmente, es periférico si .${\displaystyle d}$${\displaystyle d}$${\displaystyle v}$${\displaystyle \epsilon (v)=d}$

Un vértice pseudoperiférico tiene la propiedad de que para cualquier vértice , si está lo más lejos posible, entonces está lo más lejos posible. Formalmente, un vértice u es pseudo-periférica, si para cada vértice v con bodegas .${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)=\epsilon (u)}$${\displaystyle \epsilon (u)=\epsilon (v)}$

La partición de los vértices de un gráfico en subconjuntos por sus distancias desde un vértice inicial dado se denomina estructura de nivel del gráfico.

Un gráfico tal que por cada par de vértices hay una ruta única más corta que los conecta se llama gráfico geodésico . Por ejemplo, todos los árboles son geodésicos. ^[4]

Algoritmo para encontrar vértices pseudoperiféricos

A menudo, los algoritmos de matriz dispersa periférica necesitan un vértice inicial con una excentricidad alta. Un vértice periférico sería perfecto, pero a menudo es difícil de calcular. En la mayoría de las circunstancias, se puede utilizar un vértice pseudoperiférico. Un vértice pseudoperiférico se puede encontrar fácilmente con el siguiente algoritmo:

1. Elija un vértice .${\displaystyle u}$
2. Entre todos los vértices que están lo más alejados posible, sea ​​uno con grado mínimo .${\displaystyle u}$${\displaystyle v}$
3. Si luego se establece y se repite con el paso 2, el caso es un vértice pseudoperiférico.${\displaystyle \epsilon (v)>\epsilon (u)}$${\displaystyle u=v}$${\displaystyle u}$

Ver también

• Matriz de distancia
• Distancia de resistencia
• Centralidad de intermediación
• Centralidad
• Cercanía
• Problema de diámetro en grados para gráficos y dígrafos
• Gráfico métrico

Notas

1. Bouttier, Jérémie; Di Francesco, P .; Guitter, E. (julio de 2003). "Distancia geodésica en gráficos planos". Física B nuclear . 663 (3): 535–567. arXiv : cond-mat / 0303272 . doi : 10.1016 / S0550-3213 (03) 00355-9 . Por distancia nos referimos aquí a la distancia geodésica a lo largo del gráfico, es decir, la longitud de cualquier camino más corto entre, digamos, dos caras dadas.
2. Weisstein, Eric W. "Gráfico geodésico" . MathWorld: un recurso web de Wolfram . Wolfram Research . Consultado el 23 de abril de 2008 . La longitud de la gráfica geodésica entre estos puntos d (u, v) se llama distancia gráfica entre u y v
3. F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
4. Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104