• Author / Uploaded
• Araceli Sanchez Olmos

Citation preview

ASIGNATURA: MATEMATICAS DISCRETAS

UNIDAD 3: DISCRETIZACION

ACTIVIDAD 2: ALGORITMOS PARA OBTENER UN ARBOL GENERADOR MINIMO

CARRERA: TSU DESARROLLO DE SOFTWARE

MATRICULA: 1911002451

ALUMNA: ARACELI SANCHEZ OLMOS

DOCENTE: JORGE ALBERTO HERNANDEZ BENAVIDEZ

GRUPO: DS DMDI – 2002 – B2 – 005

NOVIEMBRE 2020

1

Portada

1

Contenido

2

Grafo Pipa

2

Encontrar árbol y peso

3

Tabla escolar

4

Referencias

5

Conclusión

5

1. El siguiente grafo no dirigido representa el recorrido que tiene que cubrir una PIPA de la empresa “PEMEX” para proporcionar combustible a diferentes gasolineras para su venta, se desea conocer cuál será la mejor ruta para seguir, con el fin de ahorrar tiempo y subministrar combustible a todas las gasolinerías durante un mismo día.

a)

Realizar el grafo no dirigido del problema planteado en un software especializado para modelar grafos.

2

b) Encontrar el árbol generador mínimo mediante el algoritmo de Prim. Agrega la solución mediante software especializado, no olvides resaltar las aristas que forman el árbol generador mínimo

c)

¿Cuál es el peso total de árbol generador mínimo para este problema? Peso total: 324

d)

Explica los pasos de forma breve de la aplicación del algoritmo de Prim.

Los pasos los hizo el programa yo solo me enfoque en las indicaciones del programa Magra Da e) ¿Crees que si aplicas el algoritmo de Kruskal a este problema el resultado será el mismo? Explica ¿Por qué? R= Si da el mismo resultado, según lo que entendí es que los algoritmos son muy parecidos por eso da el mismo resultado

3

2. La siguiente tabla representa la ruta que un chofer de un autobús escolar del “Colegio México” debe seguir diariamente, debido a que el chofer desea organizar mejor sus recorridos para el ahorro de combustible y evitar retrasos al dejar a los niños en la escuela se desea conocer la mejor ruta para realizar su actividad de la forma más eficiente. PUNTO SALIDA A A B C C E H G G I I

PUNTO DE LLEGADA B G C D F H F F E H D

Distancia en Km 3 4 2 4 2 4 5 4 6 3 1

a)

A partir de la tabla anterior realizar el grafo no dirigido del problema planteado en un software especializado para modelar grafos.

b)

Encontrar el árbol generador mínimo mediante el algoritmo de Kruskal. Agrega la solución mediante software especializado, no olvides resaltar las aristas que forman el árbol generador mínimo

4

c)

¿Cuál es el peso total de árbol generador mínimo para este problema? Peso total: 23

d)

Explica los pasos de forma breve de la aplicación del algoritmo de Kruskal.

Loa pasos fueron que abrí el programa, y forme el grafo, después busque el algoritmo en el mismo programa y se formó el árbol generador. e) ¿Crees que si aplicas el algoritmo de Prim a este problema el resultado será el mismo? Explica ¿Por qué? Si, el resultado es el mismo, será porque sigue el mismo camino para formar el árbol.

Conclusión: En conclusión, los dos algoritmos son realmente útiles para solucionar cualquier problema de arboles generadores mínimos y si vamos a compararlos se podría decir que es mas sencillo trabajar con el algoritmo de Kruskal. EcuRed. (2012). Algoritmo de Kruskal. 18/11/2020, de EcuRed Sitio web: https://www.ecured.cu/Algoritmo_de_Kruskal

N/A. (2020). Algoritmos de Kruskal y Prim. 18/11/2020, de wextensible Sitio web: https://www.wextensible.com/temas/voraces/kruskal-prim.html

5