Hispanopedia Wiki
Articulo de referencia

Árbol de camino más corto

Ejemplo de uno de dos árboles de camino más corto donde el vértice raíz es el cuadrado rojo. Las aristas del árbol están indicadas con líneas verdes, mientras que las dos líneas...

Hispanopedia WikiContenido en espanolLectura gratuita
Un ejemplo sencillo de un árbol de camino más corto.
Ejemplo de uno de dos árboles de camino más corto donde el vértice raíz es el cuadrado rojo. Las aristas del árbol están indicadas con líneas verdes, mientras que las dos líneas discontinuas representan aristas del grafo completo que no forman parte del árbol. Los números junto a los vértices indican la distancia desde el vértice raíz.

En matemáticas e informática , un árbol de camino más corto con raíz en un vértice v de un grafo conectado y no dirigido G es un árbol de expansión T de G , de tal manera que la distancia del camino desde la raíz v a cualquier otro vértice u en T es la distancia del camino más corto desde v a u en G.

En grafos conectados donde los caminos más cortos están bien definidos (es decir, donde no hay ciclos de longitud negativa), podemos construir un árbol de caminos más cortos utilizando el siguiente algoritmo:

  1. Calcula dist( u ), la distancia del camino más corto desde la raíz v hasta el vértice u en G utilizando el algoritmo de Dijkstra o el algoritmo de Bellman-Ford .
  2. Para todos los vértices que no son raíz u , podemos asignar a u un vértice padre p u tal que p u esté conectado a u , y que dist( p u ) + edge_dist( p u , u ) = dist( u ). En caso de que existan varias opciones para p u , se elige p u para la cual exista un camino más corto desde v hasta p u con la menor cantidad de aristas posible; esta regla de desempate es necesaria para evitar bucles cuando existen ciclos de longitud cero.
  3. Construye el árbol de ruta más corta utilizando las aristas entre cada nodo y su padre.

El algoritmo anterior garantiza la existencia de árboles de camino más corto. Al igual que los árboles de expansión mínima , los árboles de camino más corto en general no son únicos.

En los grafos donde todos los pesos de las aristas son iguales, los árboles de ruta más corta coinciden con los árboles de búsqueda en anchura .

En los grafos que tienen ciclos negativos, el conjunto de caminos simples más cortos desde v a todos los demás vértices no necesariamente forman un árbol.

Para grafos conectados simples, los árboles de caminos más cortos pueden usarse [ 1 ] para sugerir una relación no lineal entre dos medidas de centralidad de red : cercanía y grado . Suponiendo que las ramas de los árboles de caminos más cortos son estadísticamente similares para cualquier nodo raíz en una red, se puede demostrar que el tamaño de las ramas depende solo del número de ramas conectadas al vértice raíz, es decir, del grado del nodo raíz. De esto se deduce que el inverso de la cercanía, una escala de longitud asociada a cada vértice, varía aproximadamente de forma lineal con el logaritmo del grado. La relación no es exacta, pero captura una correlación entre cercanía y grado en un gran número de redes construidas a partir de datos reales [ 1 ] y este éxito sugiere que los árboles de caminos más cortos pueden ser una aproximación útil en el análisis de redes.

Véase también

Referencias

  1. 1 2 Evans, Tim S.; Chen, Bingsheng (2022). "Vinculando las medidas de centralidad de red cercanía y grado" . Communications Physics . 5 (1): 172. arXiv : 2108.01149 . Bibcode : 2022CmPhy...5..172E . doi : 10.1038/s42005-022-00949-5 . hdl : 10044/1/97904 . ISSN 2399-3650 . 

Referencias

Cahn, Robert S. (1998). Diseño de redes de área amplia: conceptos y herramientas para la optimización . Redes. Morgan Kaufmann. ISBN 978-1558604582.