Por Juan Sánchez Mora – Estudiante de la carrera de Ingeniería Informática

Se sabe muy bien que el ser humano siempre ha buscado la forma más sencilla de encontrar una solución, como por ejemplo buscar la forma más sencilla de hacer un recorrido de un punto al otro y devolverse por un diferente recorrido. En este artículo se buscará explicar cómo funcionan los grafos y los Sistemas de Información Geográfica.  Primero, ¿qué es un grafo? Se conoce como grafo el conjunto de objetos que se llaman vértices o nodos, y están unidos por líneas llamadas aristas. Los grafos nos permiten estudiar la relación que tiene los nodos entre ellos.

 

Como se puede observar en la imagen, tenemos 3 vértices y 3 aristas. La primera vez que se usó un grafo fue en 1736 por Leonhard Euler, quien buscaba la solución del problema de los puentes de Konigsberg. Los grafos pueden ser dirigidos, no dirigidos o etiquetados (Chirinos, 2010).

Los grafos dirigidos son aquellos que se representan mediante una flecha en la arista. Esto significa que un nodo (A) puede tener una relación con otro nodo (B), pero el nodo (A) no tiene relación con el nodo (C). Véase el siguiente ejemplo:

 

Como se puede ver, el nodo A tiene relación con el B, el nodo B la tiene con el nodo C, pero, al tener dirección, no pueden tener relación al revés.Por su parte, los grafos no dirigidos son los grafos cuyas aristas no tienen dirección. Esto significa que se puede recorrer en cualquier dirección, siempre y cuando los nodos estén conectados mediante las aristas, como se puede observar en el gráfico 1. (Chirinos, 2010).

Los grafos etiquetados se representan dándole a las aristas un peso, ya sea un número, un nombre u otros datos. A estos grafos pueden trabajar con grafos dirigidos y no dirigidos. Un ejemplo de estos puede ser la distancia en metros que se deben recorrer para llegar a la casa de un amigo.

 

Los grafos tienen muchos tipos de aplicaciones, tanto de mapas como aplicaciones matemáticas, como resolver problemas sobre búsqueda de caminos con el menor costo, por ejemplo, la ruta que usará el taxi para llevar a una persona a su destino. Otra aplicación puede ser la del teorema de los 4 colores, normalmente se usa para pintar mapas y, como el nombre lo dice, con 4 colores. Lo que busca es colorear los vértices del grafo sin que haya el mismo color a la par del vértice. Una aplicación matemática en los grafos, muy conocida, es la del algoritmo de Floyd y Warshall. Este algoritmo tiene como objetivo buscar el camino más corto en grafos etiquetados o ponderados.

Sistemas de Información Geográfica

Se entiende como Sistema de Información Geográfica el grupo de datos que están relacionados en un espacio físico, que permite que los usuarios finales puedan crear, añadir, analizar y representar de una forma eficiente el tipo de información geográfica que esté asociada a un territorio. Dicha información geográfica debe tener un componente espacial, es decir, una ubicación y también debe tener un componente atributivo; este será el que dé con más detalle lo que se busca.

Algunos usos para los que han servido estos sistemas en Costa Rica son el manejo de cuencas hidrográficas, en el manejo y la conservación de los recursos naturales, monitoreo ambiental, entre otros. Como se tiene por entendido, estos sistemas facilitan la visualización de datos que se han obtenido de un mapa, con el fin de mostrar y comparar fenómenos geográficos de cualquier tipo, como pueden ser la identificación de parcelas agrícolas o la densidad de una población en algún lugar que se esté buscando. También permite consultar y mostrar los resultados en dispositivos móviles de forma ágil para resolver problemas complejos de planificación y su gestión; esto ha ayudado bastante a la hora de la toma de decisiones (Solano, s.f.).

En conclusión, los grafos y los Sistemas de Información Geográfica tienen usos similares, como pueden ser la búsqueda de caminos que queden mejor para un cliente a la hora de tomar un taxi o para ver cuánta población puede haber en cierta área del país. También se entiende que los grafos y los SIG nos han ayudado a la toma de decisiones para resolver problemas complejos.

 

MOXIE es el Canal de ULACIT (www.ulacit.ac.cr), producido por y para los estudiantes universitarios, en alianza con el medio periodístico independiente Delfino.cr, con el propósito de brindarles un espacio para generar y difundir sus ideas.  Se llama Moxie - que en inglés urbano significa tener la capacidad de enfrentar las dificultades con inteligencia, audacia y valentía - en honor a nuestros alumnos, cuyo “moxie” los caracteriza.

Referencias bibliográficas:
• Chirinos, N. (14 de noviembre de 2010). Teoría de Grafos. Conceptos Básicos. Recuperado de https://es.slideshare.net/naborchirinos/conceptos-teoria-de-grafos-5778778
• Solano, M. (s.f.). Los Sistemas de Información Geográfica: conceptos y utilización. Revista Geográfica de América Central. Recuperado de https://www.revistas.una.ac.cr/index.php/geografica/article/view/3002