Distancia (teoría de grafos)

En la teoría de grafos, la distancia entre dos vértices de un gráfico es el número de aristas en el camino más corto (también llamado geodésico del gráfico ). Una distancia en un gráfico también se llama distancia geodésica [1] . Puede haber varios caminos más cortos entre dos vértices [2] . Si no hay camino entre dos vértices, es decir, si pertenecen a diferentes componentes conexas , entonces se acostumbra considerar que la distancia es infinita.

En el caso de grafos dirigidos, la distancia entre dos vértices y se define como la longitud del camino más corto de a , formado por arcos [3] . A diferencia del caso de los grafos no dirigidos, puede no coincidir con , e incluso puede ocurrir que una distancia exista y la otra no. ${\ estilo de visualización d (u, v)}$ $tu$ $v$ $tu$ $v$ ${\ estilo de visualización d (u, v)}$ ${\ estilo de visualización d (v, u)}$

Definiciones básicas

Un espacio métrico definido en un conjunto de puntos en términos de distancia en un gráfico 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 de un vértice es la distancia geodésica más grande entre y cualquier otro vértice en el gráfico. Es decir, la distancia a la más lejana de la parte superior del gráfico. ${\ estilo de visualización \ épsilon (v)}$ $v$ $v$ $v$

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

El radio del gráfico es la excentricidad mínima entre todos los vértices del gráfico. $r$

r=\min _{v\in V}\epsilon (v)

El diámetro del gráfico es la excentricidad máxima entre todos los vértices del gráfico. Por lo tanto, es la mayor distancia entre todos los pares de vértices del gráfico $d$ $d$

d=\max _{v\in V}\epsilon (v)

Para encontrar el diámetro de un gráfico, primero encuentra los caminos más cortos entre todos los pares de vértices . La mayor longitud del camino más corto es el diámetro del gráfico.

El vértice central de la gráfica con radio es un vértice cuya excentricidad es igual a . Es decir, el vértice en el que se alcanza el radio. $r$ $r$

{\ estilo de visualización \ épsilon (v) = r}

El vértice periférico de la gráfica del diámetro es el vértice cuya excentricidad es igual a $d$ $d$

{\ estilo de visualización \ épsilon (v) = d}

Un vértice pseudoperiférico es un vértice para el cual cualquier vértice tiene la propiedad: si está lo más lejos posible, entonces lo más lejos posible. Formalmente, un vértice es pseudoperiférico si para cualquier vértice c , . $v$ $tu$ $v$ $tu$ $tu$ $v$ $tu$ $v$ ${\ estilo de visualización d (u, v) = \ épsilon (u)}$ ${\ estilo de visualización \ épsilon (u) = \ épsilon (v)}$

La división de los vértices del gráfico en subconjuntos según su distancia desde un vértice inicial dado se denomina estructura de nivel del gráfico.

Algoritmo para encontrar vértices pseudo-periféricos

A menudo, los algoritmos para matrices dispersas requieren un vértice inicial de alta excentricidad. Sería mejor usar un vértice periférico, pero en un gráfico grande es difícil encontrarlo. En la mayoría de los casos, se pueden utilizar vértices pseudoperiféricos. El vértice pseudoperiférico se puede encontrar fácilmente usando el siguiente algoritmo:

Elijamos un top . $tu$
Entre todos los vértices más alejados de , let tiene el grado mínimo . $tu$ $v$
Si , entonces tome y vaya al paso 2, de lo contrario es un vértice pseudoperiférico. ${\ estilo de visualización \ épsilon (v)> \ épsilon (u)}$ ${\ estilo de visualización u = v}$ $v$

Véase también

Notas

↑ Jérémie Bouttier, P. Di Francesco, E. Guitter. Distancia geodésica en grafos planos. - 2003. - T. 663 , núm. 3 . - S. 535-567 . - doi : 10.1016/S0550-3213(03)00355-9 .
↑ Weisstein, Eric W. Gráfico geodésico . MathWorld: un recurso web de Wolfram . Investigación de Wolframio. - "La longitud de la gráfica geodésica entre estos puntos d(u,v) se denomina gráfica distancia entre u y v". Consultado el 23 de abril de 2008. Archivado desde el original el 23 de abril de 2008. (indefinido)
↑ F.Harary. teoría de grafos . - MA: Addison-Wesley, 1969. - Pág . 199 .