Gráfico de la ruta más corta
En matemáticas y ciencia de la información geográfica , un gráfico de ruta más corta es un gráfico no dirigido definido a partir de un conjunto de puntos en el plano euclidiano . El gráfico de la ruta más corta se propone con la idea de inferir bordes entre un conjunto de puntos de modo que la ruta más corta tomada sobre los bordes inferidos se alinee aproximadamente con la ruta más corta tomada sobre la región imprecisa representada por el conjunto de puntos. El conjunto de bordes del gráfico de la ruta más corta varía en función de un solo parámetro t ≥ 1. Cuando el peso de un borde se define como su longitud euclidiana elevada a la potencia del parámetro t≥ 1, el borde está presente en el gráfico de ruta más corta si y solo si es la ruta de menor peso entre sus puntos finales. [1]
Cuando el parámetro de configuración t llega al infinito, el gráfico de la ruta más corta se convierte en el árbol de expansión mínimo del conjunto de puntos. El gráfico es un subgrafo del gráfico de Gabriel del conjunto de puntos y, por lo tanto, también un subgrafo de su triangulación de Delaunay . [1]
