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.

Formalmente, dado un grafo ${displaystyle G=(V,E)}$, la distancia entre dos vértices ${displaystyle i,jin 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]​

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)}$:

En análisis de redes sociales, el concepto se 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]​