MODELO BASADO EN GRAFOS REDUCIDOS PARA LA REPRESENTACIÓN Y ANÁLISIS DE REDES EN SISTEMAS DE INFORMACIÓN GEOESPACIAL.

Abstract

Los Sistemas de Información Geoespacial constituyen una importante herramienta para el apoyo a la toma de decisiones. Entre sus diversas aplicaciones se puede mencionar la búsqueda de caminos óptimos. Uno de los modelos más utilizados para realizar búsqueda de caminos óptimos es el modelo de grafo. Se han definido varios algoritmos de reducción de grafos con el objetivo de disminuir el tiempo de respuesta a los usuarios, pero en todos los casos se pueden utilizar en ámbitos muy específicos debido a que dichos algoritmos no garantizan que no haya pérdida de información. La presente tesis tiene como objetivo principal desarrollar un modelo para la representación y análisis de redes basado en grafos, que permita reducir el número de nodos sin perder información y que garantice escalabilidad y eficiencia en la búsqueda de caminos óptimos cuando las redes son grandes. Los principales aportes de esta investigación son: un modelo que contribuye a la realización eficiente de búsquedas de caminos óptimos en grafos grandes, el diseño de un algoritmo que reduce un grafo sin pérdida de información y que permite obtener el grafo original a partir del reducido, una modificación del algoritmo de Dijkstra para la búsqueda de caminos óptimos en grafos reducidos con el algoritmo propuesto en este trabajo, una biblioteca de clases que implementa el modelo propuesto, un plugin para el sistema Quantum GIS, que realiza búsqueda de caminos óptimos haciendo uso de la biblioteca de clases implementada y la aplicación del algoritmo de reducción a un entorno diferente a los Sistemas de Información Geoespacial, específicamente al Método de los Grafos Dicromáticos. Este método ha sido utilizado en el Diseño Racional en Ingeniería Mecánica.