Distancia (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Red de nodos mostrando los divisores. En el grafo se puede ver que la distancia entre 1 y 6 es 1 debido a que puede recorrerse de forma mínima tanto por 1-2-6 como por 1-3-6. De la misma forma la distancia entre 1 y 12 es 2 de cualquier forma.

En teoría de grafos se denomina distancia entre dos vértices de un grafo al número de vértices mínimo que debe recorrerse para unirlos. La distancia entre dos nodos de un grafo es la longitud del camino más corto (a veces se denomina geodésico[1] ). Si no hubiera conexión alguna entre dos vértices se dice que la distancia es infinita. Las distancias de todos los vértices de un grafo se computan en lo que se denomina matriz de distancias. el concepto se emplea en las mediadas de centralidad de redes.

Aplicaciones[editar]

Existen numerosas aplicaciones en la teoría de grafos en las que interviene el concepto de distancia, por ejemplo en el diseño de grandes interiores, tales como los aeropuertos donde el concepto distancia supone el conocimiento del tiempo necesario para llegar a un punto cualesquiera del mismo. Es uno de los conceptos clave en las redes de mundo pequeño.

Véase también[editar]

Referencias[editar]