Distancia (teoría de grafos)

Distancia (teoría de grafos)

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 empela en las mediadas de centralidad de redes.

Aplicaciones

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

Referencias

  1. Bouttier, Jérémie; Di Francesco,P. ,Guitter, E. (July de 2003). «Geodesic distance in planar graphs» Nuclear Physics B. Vol. 663. n.º 3. pp. 535–567. DOI 10.1016/S0550-3213(03)00355-9.
Obtenido de "Distancia (teor%C3%ADa de grafos)"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Estrella (teoría de grafos) — Estrella S7. En teoría de grafos, una estrella Sk es el grafo bipartito completo K1,k, un árbol con un vértice interno y k hojas. Una estrella con 3 aristas se conoce en inglés como claw (garra o garfio). La estrella Sk es tran …   Wikipedia Español

  • Centralidad — Saltar a navegación, búsqueda Un ejemplo de centralidad se muestra en el grafo de la ilustración, la intermediación se grada mediante colores que van desde el rojo con un bajo valor de intermediación hasta el azul con un valor máximo. Dentro de… …   Wikipedia Español

  • Topología — Para otros usos de este término, véase Topología (desambiguación). Ilustración del Teor …   Wikipedia Español

  • Problema del viajante — Saltar a navegación, búsqueda Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida? Contenido …   Wikipedia Español

  • Coeficiente de agrupamiento — Ejemplo de coeficiente de agrupamiento en un [[[grafo no dirigido]] en el que se considera el nodo sombreado on an undirected graph for the shaded node i. Los segmentos de líneas negras son enlaces que conectan vecinos de i, y los segmentos… …   Wikipedia Español

  • Anexo:Matemáticos importantes — En esta lista de matemáticos importantes se presenta una selección de matemáticos desde la antigüedad hasta el presente. La selección se orienta por los aportes científicos, utilizando como criterio para definir el grado de notoriedad la atención …   Wikipedia Español

  • Historia de la matemática — Página del Compendio de cálculo por el método de completado y balanceado de Muhammad ibn Mūsā al Khwārizmī (820 d.C.) La historia de las matemáticas es el área de estudio que abarca las investigaciones sobre los orígenes de los descubrimi …   Wikipedia Español

  • Grafo cuadrado — Un grafo cuadrado. En teoría de grafos, un grafo cuadrado es un grafo no dirigido que puede dibujarse en el plano de modo que cada superficie acotada es un cuadrilátero y cada vértice con tres o menos vecinos es incidente a una cara no acotada.… …   Wikipedia Español

  • Árbol binario — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.