Distancia (teoría de grafos)

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.

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.

Definición formal

Formalmente, dado un grafo ${\displaystyle G=(V,E)}$, la distancia entre dos vértices ${\displaystyle i,j\in V}$ se puede denotar como ${\displaystyle d(i,j)}$. Si los vértices no son accesibles, entonces se asume que ${\displaystyle d(i,j)=\infty }$. Si el grafo es no dirigido, entonces ${\displaystyle d(i,j)=d(j,i)}$; sin embargo, si el grafo es dirigido, la distancia puede diferir dependiendo del sentido de las aristas.^[1]​

Conceptos derivados

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 ${\displaystyle n}$ vértices varía entre ${\displaystyle 1}$ y ${\displaystyle n-1}$. 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 ${\displaystyle 1}$ (para un grafo completo) y ${\displaystyle n-1}$ (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 ${\displaystyle G=(V,E)}$:

• La excentricidad de un vértice ${\displaystyle i\in V}$ es ${\displaystyle \textstyle \max _{j}d(i,j)}$, para todo ${\displaystyle \textstyle j\in V\setminus \{i\}}$.^[1]​
• El diámetro de ${\displaystyle G}$ es ${\displaystyle \textstyle \max _{i}\max _{j}d(i,j)}$, para todo ${\displaystyle \textstyle i,j\in V}$.^[1]​

Aplicaciones

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

• Matriz de distancias

Referencias

1. 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

• 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. 

• Datos: Q2742711