Distancia (teoría de grafos)

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Grafo que representa los divisores del número 12. La distancia entre 1 y 6 es 2, por los caminos 1-2-6 o 1-3-6. La distancia entre 1 y 12 es 3.

En teoría de grafos se denomina distancia o distancia geodésica entre dos vértices o nodos de un grafo a la longitud o número de aristas del camino más corto entre ellos.[1][2]​ Si dos vértices no son accesibles a través de un camino, entonces la distancia entre ellos es infinita.[1]​ Las distancias de todos los vértices de un grafo se pueden representar mediante una matriz de distancias.

Definición formal[editar]

Formalmente, dado un grafo , la distancia entre dos vértices se puede denotar como . Si los vértices no son accesibles, entonces se asume que . Si el grafo es no dirigido, entonces ; sin embargo, si el grafo es dirigido, la distancia puede diferir dependiendo del sentido de las aristas.[1]

Conceptos derivados[editar]

La excentricidad o número de asociación de un vértice en un grafo conexo es la mayor distancia entre ese nodo y cualquier otro del grafo.[3][4]​ La excentricidad de cualquier grafo no dirigido conexo o de cualquier grafo dirigido fuertemente conexo de vértices varía entre y . En cambio, la excentricidad de un grafo dirigido débilmente conexo o unilateralmente conexo puede estar indefinida (esto es, infinita). El diámetro de un grafo es la mayor excentricidad entre todos los vértices del grafo; este valor puede variar entre (para un grafo completo) y (por ejemplo, para un grafo camino). Aunque el diámetro de un grafo disconexo sea infinito, el diámetro de sus componentes conexas será siempre finito.[1]

Formalmente, dado un grafo :

  • La excentricidad de un vértice es , para todo .[1]
  • El diámetro de es , para todo .[1]

Aplicaciones[editar]

En análisis de redes sociales, el concepto de distancia se utiliza para definir medidas de centralidad, así como para construir ciertos tipos de subgrupos cohesivos. Por ejemplo, para una red de comunicaciones, el diámetro permite conocer la distancia máxima necesaria para poder transmitir un mensaje.[1]

Véase también[editar]

Referencias[editar]

  1. a b c d e f g Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
  2. Bouttier, J.; Di Francesco, P.; Guitter, E. (2003). «Geodesic distance in planar graphs». Nuclear Physics B 663 (3): 535-567. doi:10.1016/S0550-3213(03)00355-9. 
  3. Harary, F.; Norman, R. Z. (1953). Graph theory as a mathematical model in social science. Ann Arbor: University of Michigan Press. 
  4. Harary, F. (1969). Graph theory. Reading, MA: Addison-Wesley. 

Bibliografía[editar]

  • Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.