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.

Si los vértices no son accesibles, entonces se asume que

; 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

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

Aunque el diámetro de un grafo disconexo sea infinito, el diámetro de sus componentes conexas será siempre finito.

Por ejemplo, para una red de comunicaciones, el diámetro permite conocer la distancia máxima necesaria para poder transmitir un mensaje.