Distancia (teoría de grafos)

Longitud del camino más corto entre dos nodos de un gráfico

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 (también llamado gráfico geodésico ) que los conecta. Esto también se conoce como distancia geodésica o distancia del camino más corto . ^[1] Observe que puede haber más de un camino más corto entre dos vértices. ^[2] Si no hay un 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 de un camino dirigido más corto de u a v que consta de arcos, siempre que exista al menos uno de esos caminos. ^[3] Observe que, en contraste con el caso de los gráficos no dirigidos, d ( u , v ) no necesariamente coincide con d ( v , u ) , por lo que es solo una cuasimétrica , y podría darse el caso de que uno está definido mientras que el otro no.

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 gráfico no dirigido) y la función de distancia forman un espacio métrico, si y sólo si el gráfico es conexo .

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

${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$

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

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

${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}$

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

${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}$

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.

Un vértice central en una gráfica de radio r es aquel cuya excentricidad es r —es decir, un vértice cuya distancia desde su vértice más lejano es igual al radio, equivalentemente, un vértice v tal que ϵ ( v ) = r .

Un vértice periférico en una gráfica de diámetro d es aquel cuya excentricidad es d , es decir, un vértice cuya distancia desde su vértice más alejado es igual al 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 u está lo más lejos posible de v , entonces v está lo más lejos posible de u . Formalmente, un vértice v es pseudoperiférico si, para cada vértice u con d ( u , v ) = ϵ ( v ) , se cumple que ϵ ( u ) = ϵ ( v ) .

Una estructura de niveles del gráfico, dado un vértice inicial, es una partición de los vértices del gráfico en subconjuntos por sus distancias desde el vértice inicial.

Un gráfico geodésico es aquel en el que cada par de vértices tiene un camino único más corto que los conecta. Por ejemplo, todos los árboles son geodésicos. ^[4]

La distancia ponderada del camino más corto 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 ^W ( u , v ) es la suma mínima de pesos en todos los caminos. conectando u y v . Consulte el problema del camino más corto para obtener más detalles y algoritmos.

Algoritmo para encontrar vértices pseudoperiféricos.

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

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

Ver también

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

Notas

1. Boutier, Jérémie; Di Francesco, P.; Guitter, E. (julio de 2003). "Distancia geodésica en gráficos planos". Física Nuclear B. 663 (3): 535–567. arXiv : cond-mat/0303272 . Código bibliográfico : 2003NuPhB.663..535B. doi :10.1016/S0550-3213(03)00355-9. S2CID  119594729. 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 . Investigación Wolfram. Archivado desde el original el 23 de abril de 2008 . Consultado el 23 de abril de 2008 . La longitud del gráfico geodésico entre estos puntos d(u,v) se llama distancia del gráfico entre u y v.
3. F. Harary, Teoría de grafos, Addison-Wesley, 1969, p.199.
4. Øystein Ore , Teoría de grafos [3.ª ed., 1967], Publicaciones del Coloquio, Sociedad Matemática Estadounidense, p. 104