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 . [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 un camino dirigido más corto desde a consiste en arcos, siempre que exista al menos uno de esos caminos. [3] Nótese que, a diferencia del caso de los gráficos no dirigidos, no necesariamente coincide con , y podría darse el caso de que uno esté definido y el otro no.
Conceptos relacionados
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 y 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 un gráfico es la excentricidad mínima de cualquier vértice o, en símbolos, .
El diametro de un gráfico es la excentricidad máxima de cualquier vértice del gráfico. Es decir, es la mayor distancia entre cualquier par de vértices o, alternativamente, . Para encontrar el diámetro de un gráfico, primero encuentre el camino más corto entre cada par de vértices . La mayor longitud de cualquiera de estos caminos es el diámetro del gráfico.
Un vértice central en una gráfica de radio es uno cuya excentricidad es —Es decir, un vértice que alcanza el radio o, de forma equivalente, un vértice tal que .
Un vértice periférico en una gráfica de diámetro es uno que es distancia de algún otro vértice, es decir, un vértice que alcanza el diámetro. Formalmente, es periférico si .
Un vértice pseudoperiférico tiene la propiedad de que para cualquier vértice , Si está tan lejos de como sea posible, entonces está tan lejos de como sea posible. Formalmente, un vértice u es pseudoperiférico, si para cada vértice v con sostiene .
La partición de los vértices de un gráfico en subconjuntos por sus distancias desde un vértice inicial dado se denomina estructura de nivel del gráfico.
Un gráfico tal que por cada par de vértices hay una ruta única más corta que los conecta se llama gráfico geodésico . Por ejemplo, todos los árboles son geodésicos. [4]
Algoritmo para encontrar vértices pseudoperiféricos
A menudo, los algoritmos de matriz dispersa periférica necesitan un vértice inicial con una excentricidad alta. Un vértice periférico sería perfecto, pero a menudo es difícil de calcular. En la mayoría de las circunstancias, se puede utilizar un vértice pseudoperiférico. Un vértice pseudoperiférico se puede encontrar fácilmente con el siguiente algoritmo:
- Elige un vértice .
- Entre todos los vértices que están tan lejos de como sea posible, deja ser uno con un grado mínimo .
- Si luego establece y repita con el paso 2, de lo contrario es un vértice pseudoperiférico.
Ver también
Notas
- ^ Bouttier, Jérémie; Di Francesco, P .; Guitter, E. (julio de 2003). "Distancia geodésica en gráficos planos". Física B nuclear . 663 (3): 535–567. arXiv : cond-mat / 0303272 . doi : 10.1016 / S0550-3213 (03) 00355-9 .
Por distancia queremos decir aquí la distancia geodésica a lo largo del gráfico, es decir, la longitud de cualquier camino más corto entre, digamos, dos caras dadas.
- ^ Weisstein, Eric W. "Graph Geodesic" . MathWorld: un recurso web de Wolfram . Wolfram Research . Consultado el 23 de abril de 2008 .
La longitud de la gráfica geodésica entre estos puntos d (u, v) se llama distancia gráfica entre u y v
- ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
- ↑ Øystein Ore , Theory of graphs [3ª ed., 1967], Publicaciones del coloquio, American Mathematical Society, p. 104