Distancia (teoría de grafos)

Longitud de la ruta más corta 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 grafo es el número de aristas en una ruta más corta (también llamada geodésica del grafo ) que los conecta. Esto también se conoce como distancia geodésica o distancia de ruta más corta . ^[1] Nótese que puede haber más de una ruta más corta 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 grafo 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 consiste en arcos, siempre que exista al menos uno de dichos caminos. ^[3] 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 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 grafo definido sobre el conjunto se denomina métrica de grafo . El conjunto de vértices (de un grafo no dirigido) y la función de 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,

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

Se puede pensar como la distancia a la que se encuentra un nodo del nodo más distante de él en el gráfico.

El radio r de un gráfico 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 grafo es la excentricidad máxima de cualquier vértice del grafo. Es decir, d es la distancia máxima 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 hallar el diámetro de un grafo, primero hay que hallar el camino más corto entre cada par de vértices . La mayor longitud de cualquiera de estos caminos es el diámetro del grafo.

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

Un vértice periférico en un grafo 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 alejado posible de v , entonces v está lo más alejado 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 nivel 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 grafo geodésico es aquel en el que cada par de vértices tiene un camino más corto único que los conecta. Por ejemplo, todos los árboles son geodésicos. ^[4]

La distancia ponderada de la ruta más corta generaliza la distancia geodésica a los grafos ponderados . En este caso, se supone que el peso de una arista representa su longitud o, para redes complejas, el costo de la interacción, y la distancia ponderada de la ruta más corta d ^W ( u , v ) es la suma mínima de los pesos de todas las rutas que conectan u 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 matrices dispersas periféricas 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, de lo contrario es un vértice pseudoperiférico. ${\displaystyle \epsilon (v)>\epsilon (u)}$ ${\displaystyle u=v}$ ${\displaystyle u}$

Véase también

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

Notas

1. Bouttier, Jérémie; Di Francesco, P.; Guitter, E. (julio de 2003). "Geodesic distance in planar graphs" (Distancia geodésica en grafos planos). Nuclear Physics B. 663 ( 3): 535–567. arXiv : cond-mat/0303272 . Bibcode :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 grafo, es decir, la longitud de cualquier camino más corto entre, por ejemplo, dos caras dadas.
2. Weisstein, Eric W. "Geodésica gráfica". MathWorld--A Wolfram Web Resource . Wolfram Research. Archivado desde el original el 23 de abril de 2008. Consultado el 23 de abril de 2008. La longitud de la geodésica gráfica entre estos puntos d(u,v) se denomina distancia gráfica entre u y v.
3. F. Harary, Teoría de grafos, Addison-Wesley, 1969, pág.199.
4. Øystein Ore , Teoría de grafos [3.ª ed., 1967], Colloquium Publications, American Mathematical Society, pág. 104