GRAFOS

Proyecto Final de matematica discreta:

Integrantes: Carnet: Wualder Daniel Gomez Lepe 1490-05-11625 Erick Eduardo Berber Maldonado 1490-21-11326 Jairo Alexis Juan Sac Tay 1490-21-5002 Oswaldo Daniel Gervacio Itzep 1490-21-8611 Marc Augusto Xavier Chavaloc Pérez 1490-21-6408

Introducción

En el presente trabajo se presenta una corta definicion de un grafo, uno de los algoritmos para encnatrar la ruta mas corta entre dos puntos y una posible solución a un grafo que va de un destino de A a B, A a C, B a C etc…, Con este programa se desea solucionar el exceso de costos buscando la ruta más cercana.

Ejemplo:

Usos de un grafo:

¿Que es un grafo?

Un grafo es un conjunto de elementos “x”, denominados vértices o nodos y cuantan con uniones "aristas", este puede se visto como un listado de parejas de vértices E que expresa las relaciones entre dichos elementos. Si no se considera el orden de los vértices en cada pareja decimos que el grafo es no orientado.

Ruta más corta:

A ->C = 10

Algoritmo de rutas más cortas de grafos.

Ejemplo:

(DIJKASTRA):

El algoritmo de rutas más cortas es en uno de los módulos de análisis más importantes de los algoritmos de grafos Este se encarga de detectar dentro de un grafo cuál es la ruta más eficiente o el recorrido de menor distancia entre un par de vértices que conforman un grafo.

NODO PRINCIPAL

Se utilizo como eje "NODO =0" la CIUDAD CAPITAL para así este siempre sea un inicio y este no tendrá un eje exacto. También podemos tomar cualquier punto de partida utilizando la distancia en KM del departamento de salida al punto final de llegada.

Grafo base del proyecto

Ruta más corta:

Ruta intermedia:

A -> B-> I= 56

A -> H-> I= 98

Ruta más larga:

A -> I = 59

EJEMPLO: Recorrido del grafo en el algoritmo.

Prueba del algoritmo

¡Gracias!