Distancia (teoría de grafos)

En el campo matemático de la teoría de grafos, la distancia entre dos vértices en un gráfico es el número de aristas en un camino más corto que los conecta. Esto también se conoce como distancia geodésica o distancia del camino más corto. Observe que puede haber más de un camino más corto entre dos vértices. Si no hay camino 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 d (u, v) entre dos vértices u y v se define como la longitud del camino dirigido más corto de u a v que consiste en arcos, siempre que exista al menos uno de esos caminos. Nótese que, en contraste con el caso de grafos no dirigidos, d (u, v) no necesariamente coincide con d (v, u) —por lo que es solo una cuasi-métrica, y podría darse el caso de que uno esté definido mientras el otro no lo es.

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 llama gráfico métrico. El conjunto de vértices (de un grafo no dirigido) y la función distancia forman un espacio métrico, si y solo si el grafo es conexo.

La excentricidad ϵ (v) de un vértice v es la mayor distancia entre v y cualquier otro vértice; en símbolos,

Se puede pensar en qué tan lejos está un nodo del nodo más distante en el gráfico.

El radio r de un gráfico es la excentricidad mínima de cualquier vértice o, en símbolos,

El diámetro d de un gráfico es la excentricidad máxima de cualquier vértice en el gráfico. Es decir, d es la mayor distancia entre cualquier par de vértices o, alternativamente,

Para encontrar el diámetro de un gráfico, primero encuentra 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.

Un vértice central en un gráfico de radio r es aquel cuya excentricidad es r, es decir, un vértice que alcanza el radio o, equivalentemente, un vértice v tal que ϵ (v) = r.

Un vértice periférico en un gráfico de diámetro d es uno que está a una distancia d de algún otro vértice, es decir, un vértice que alcanza el diámetro. Formalmente, v es periférico si ϵ (v) = d.

Un vértice pseudoperiférico v tiene la propiedad de que para cualquier vértice u, si v está lo más lejos posible de u, entonces u está lo más lejos posible de v. Formalmente, un vértice u es pseudo-periférico, si para cada vértice v con d (u, v) = ϵ (u) se cumple ϵ (u) = ϵ (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 grafo tal que para cada par de vértices hay un único camino más corto que los conecta se llama grafo geodésico. Por ejemplo, todos los árboles son geodésicos.

La distancia de ruta más corta ponderada generaliza la distancia geodésica a gráficos ponderados. En este caso, se supone que el peso de un borde representa su longitud o, para redes complejas, el costo de la interacción, y la distancia ponderada del camino más corto d (u, v) es la suma mínima de pesos en todos los caminos que conectan tu y v _ Consulte el problema de la ruta más corta para obtener más detalles y algoritmos.

Algoritmo para encontrar vértices pseudoperiféricos

A menudo, los algoritmos de matriz dispersa periférica necesitan un vértice inicial con una alta excentricidad. 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. Elige un vértice .
2. Entre todos los vértices que estén lo más lejos posible, sea uno de grado mínimo.
3. Si luego establece y repite con el paso 2, de lo contrario es un vértice pseudoperiférico.