En el campo de las matemáticas, específicamente en la teoría de grafos, la distancia entre dos vértices se define como el nómero de aristas en el camino más corto que los conecta. Este concepto es fundamental para analizar la conectividad y la eficiencia de las redes, y se conoce támbien como distancia geodésica o distancia del camino más corto.
Es importante notar que puede existir más de un camino más corto entre dos vértices. En los casos donde no existe ningën camino que conecte dos vértices (es decir, pertenecen a componentes conexos diferentes), la distancia se define convencionalmente como infinita.
Representación Computacional
Para manejar las distancias entre nodos de manera eficiente, se utiliza la matriz de distancia (también llamada matriz de caminos más cortos para todos los pares). Esta es una matriz cuadrada donde cada entrada indica la longitud del camino más corto entre dos vértices específicos.
Las matrices de distancia tienen aplicaciones cruciales en sectores como las telecomunicaciones y la química. En la teoría de grafos químicos, se derivan móltiples índices topológicos que caracterizan la estructura molecular a partir de esta matriz.
Distancia en Grafos Dirigidos
En un grafo dirigido, las aristas tienen una dirección asignada, lo que significa que el desplazamiento entre vértices no es necesariamente bidireccional. Por lo tanto, la distancia desde un nodo u hacia un nodo v puede ser diferente a la distancia desde v hacia u.
Formalmente, para los vértices u y v en un grafo dirigido G, no se garantiza que la distancia sea simétrica. Esto convierte a la distancia en grafos dirigidos en una cuasi-métrica en lugar de una métrica real.
En resumen, la distancia en grafos dirigidos depende estrictamente de la orientación de los arcos, lo que implica que la ruta de ida puede ser más corta, más larga o incluso inexistente comparada con la de vuelta.
Conceptos Relacionados
Un espacio métrico definido sobre un conjunto de puntos en términos de distancias en un grafo se denomina métrica de grafo. El conjunto de vértices de un grafo no dirigido y su función de distancia forman un espacio métrico si y solo si el grafo es conexo.
Excentricidad y Radio
La excentricidad ε(v) de un vértice v es la distancia más grande entre v y cualquier otro vértice del grafo. Representa qué tan lejos está un nodo del nodo más distante de él.
El radio r de un grafo es la excentricidad mínima de cualquier vértice del grafo.
