Grafos
El origen de la palabra grafo es griego y su significado etimológico es "trazar". aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, (ver la figura 1). En cada caso es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (nodos o vértices) con líneas conectándolos (arcos).
Ejemplo del uso de Grafo, Servicio de Entregas
Ahora veremos un ejemplo real del uso de grafos, en el que se selecciona un barrio de origen y otro de destino, la moto lo que hará es mirar la ruta que implique menos gasto, en este caso menos distancia.
Imágenes
Primero que todo, se preguntaran de donde es el mapa, bueno pues es de la ciudad de Barranquilla, Colombia, Bueno ahora si sobre el proyecto, para manejar el grafo se usan tres matrices, una matriz de identidad que es la que nos dice de que barrio a que barrio hay conexion, las segunda es la matriz de costos, esta nos dice cuanto nos cuesta ir de un barrio a otro, siempre y cuando exista la conexión entre dichos barrios.
La ultima matriz es llamada la matriz de Floyd y se usa para determinar la ruta que tenga menos costo entre dos barrios.
Aqui la imagen de las tres matrices:
Matriz Costos
Matriz de Floyd
Matriz Identidad
Donde aparecen ceros (0) o inf es por que no hay conexión. Cada columna y cada fila es un barrio.
Ademas el proyecto te permite insertar un barrio, cambiar las conexiones, aislar un barrio que no es mas que borrar todas las conexiones que este barrio tiene, salientes y entrantes. Ademas de recorrer lo barrios con una motocicleta, creas una moto y le indicas a que barrio debe ir, y puedes manejar varias motos.
Ademas el proyecto te permite insertar un barrio, cambiar las conexiones, aislar un barrio que no es mas que borrar todas las conexiones que este barrio tiene, salientes y entrantes. Ademas de recorrer lo barrios con una motocicleta, creas una moto y le indicas a que barrio debe ir, y puedes manejar varias motos.
Proyecto completo
No hay comentarios:
Publicar un comentario