Distancia (teoría de grafos)
En el campo matemático de la teoría de grafos , la distancia entre dos vértices en un grafo es el número de aristas en un camino más corto (también llamado grafo geodésico ) que los conecta. Esto también se conoce como distancia geodésica o distancia de ruta más corta . [1] Observe que puede haber más de un camino más corto entre dos vértices. [2] Si no hay una ruta que conecte los dos vértices, es decir, si pertenecen a diferentes componentes conectados , entonces convencionalmente la distancia se define como infinita.
En el caso de un gráfico dirigido, la distancia entre dos vértices y se define como la longitud de una ruta dirigida más corta de a que consta de arcos, siempre que exista al menos una de tales rutas. [3] Nótese que, a diferencia del caso de los gráficos no dirigidos, no necesariamente coincide con , por lo que es solo una cuasi-métrica , y podría darse el caso de que uno esté definido y el otro no.
Un espacio métrico definido sobre un conjunto de puntos en términos de distancias en un gráfico definido sobre el conjunto se denomina métrica de gráfico . El conjunto de vértices (de un gráfico no dirigido) y la función de distancia forman un espacio métrico, si y solo si el gráfico está conectado .
La excentricidad de un vértice es la mayor distancia entre cualquier otro vértice; en símbolos que es . Se puede pensar en qué tan lejos está un nodo del nodo más distante de él en el gráfico.
El radio de una gráfica es la excentricidad mínima de cualquier vértice o, en símbolos ,.
