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 (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,

\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,

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,

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.

A central vertex in a graph of radius $r$ is one whose eccentricity is $r$ —that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex $v$ such that $ϵ (v) = r$ .

A peripheral vertex in a graph of diameter $d$ is one whose eccentricity is $d$ —that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, $v$ is peripheral if $ϵ (v) = d$ .

A pseudo-peripheral vertex $v$ has the property that, for any vertex $u$ , if $u$ is as far away from $v$ as possible, then $v$ is as far away from $u$ as possible. Formally, a vertex $v$ is pseudo-peripheral if, for each vertex $u$ with $d (u, v) = ϵ (v)$ , it holds that $ϵ (u) = ϵ (v)$ .

A level structure of the graph, given a starting vertex, is a partition of the graph's vertices into subsets by their distances from the starting vertex.

A geodetic graph is one for which every pair of vertices has a unique shortest path connecting them. For example, all trees are geodetic.^[4]

The weighted shortest-path distance generalises the geodesic distance to weighted graphs. In this case it is assumed that the weight of an edge represents its length or, for complex networks the cost of the interaction, and the weighted shortest-path distance $d W (u, v)$ is the minimum sum of weights across all the paths connecting $u$ and $v$ . See the shortest path problem for more details and algorithms.

Algorithm for finding pseudo-peripheral vertices

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

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

Ver también

Notas

^ 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, por ejemplo, dos caras dadas.
^ 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.
^ F. Harary, Teoría de grafos, Addison-Wesley, 1969, p.199.
^ Øystein Ore , Teoría de grafos [3.ª ed., 1967], Publicaciones del Coloquio, Sociedad Matemática Estadounidense, p. 104