Skip to content

Latest commit

 

History

History
215 lines (199 loc) · 9.94 KB

README.org

File metadata and controls

215 lines (199 loc) · 9.94 KB
Raw

Proyecto 4 de la asignatura de Diseño y Análisis de Algoritmos

Desarrollador :

Yordi Edgardo Delgado Ortiz

Información:

Proyecto 04 - Algoritmos de árbol de expansión mínima Utilizando la biblioteca de grafos desarrollada en el proyecto 1, implementar los algoritmos de Kruskal (directo e inverso) y Prim de tal forma que calculen el árbol de expansión mínima; es decir, desarrollar los métodos en la clase Grafo:

  • def KruskalD(self):
  • def KruskalI(self):
  • def Prim(self):

Imágenes de los Modelos Generadas con gephi

Modelo de Mallas

30 nodos(5x6)

./Images/Mallas/Mallas_30.png

Árbol de Expansión Mínima(KruskalD)

./Images/Mallas/MST_KruskalD30_Costo.png ./Images/Mallas/Mallas_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Mallas/MST_KruskalI30_Costo.png ./Images/Mallas/Mallas_30_KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Mallas/MST_Prim_Costo30.PNG ./Images/Mallas/Mallas_30_Prim.png

500 nodos(50x10)

./Images/Mallas/Mallas_500.png

Árbol de Expansión Mínima(KruskalD)

./Images/Mallas/MST_KruskalD500_Costo.png ./Images/Mallas/MST_KruskalD500.png

Árbol de Expansión Mínima(KruskalI)

./Images/Mallas/MST_KruskalI500_Costo.PNG ./Images/Mallas/MST_KruskalI500.png

Árbol de Expansión Mínima(Prim)

./Images/Mallas/MST_Prim_Costo500.PNG ./Images/Mallas/MST_Prim500.png

Modelo de Erdos y Renyi

30 Nodos y 200 Aristas

./Images/Erdos/Erdos_30.png

Árbol de Expansión Mínima(KruskalD)

./Images/Erdos/MST_Erdos30_KruskalD_Costo.PNG ./Images/Erdos/Erdos_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Erdos/MST_Erdos30_KruskalI_Costo.PNG ./Images/Erdos/Erdos_30_KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Erdos/MST_Erdos30_Prim_Costo.PNG ./Images/Erdos/Erdos_30_Prim.png

500 Nodos y 2500 Aristas

./Images/Erdos/Erdos_500.png

Árbol de Expansión Mínima(KruskalD)

./Images/Erdos/MST_Erdos500_KruskalD_Costo.PNG ./Images/Erdos/Erdos_500_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Erdos/MST_Erdos500_KruskalI_Costo.PNG ./Images/Erdos/Erdos_500_KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Erdos/MST_Erdos500_Prim_Costo.PNG ./Images/Erdos/Erdos_500_Prim.png

Modelo de Gilbert

30 nodos y probabilidad 0.5

./Images/Gilbert/Gilbert_30 .png

Árbol de Expansión Mínima(KruskalD)

./Images/Gilbert/MST_Gilbert30_KruskalD_Costo.PNG ./Images/Gilbert/Gilbert_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Gilbert/MST_Gilbert30_KruskalD_Costo.PNG ./Images/Gilbert/Gilbert_30_KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Gilbert/MST_Gilbert30_Prim_Costo.PNG ./Images/Gilbert/Gilbert_30_Prim.png

500 nodos y probabilidad 0.02

./Images/Gilbert/Gilbert_500 .png

Árbol de Expansión Mínima(KruskalD)

./Images/Gilbert/MST_Gilbert500_KruskalD_Costo.PNG ./Images/Gilbert/Gilbert_500_ KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Gilbert/MST_Gilbert500_KruskalD_Costo.PNG ./Images/Gilbert/Gilbert_500_ KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Gilbert/MST_Gilbert500_Prim_Costo.PNG ./Images/Gilbert/Gilbert_500_ Prim.png

Modelo Geográfico

30 nodos y distancia 0.5

./Images/Geografico/geografico_30.png

Árbol de Expansión Mínima(KruskalD)

./Images/Geografico/MST_Geografico30_KruskalD_Costo.PNG ./Images/Geografico/geografico_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Geografico/MST_Geografico30_KruskalI_Costo.PNG ./Images/Geografico/geografico_30_KruskalI.png

Árbol de Expansión Mínima(KruskalI)

./Images/Geografico/MST_Geografico30_Prim.PNG ./Images/Geografico/geografico_30_Prim.png

500 nodos y distancia 0.15

./Images/Geografico/geografico_500.png

Árbol de Expansión Mínima(KruskalD)

./Images/Geografico/MST_Geografico500_KruskalD_Costo.PNG ./Images/Geografico/geografico_500_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Geografico/MST_Geografico500_Prim_Costo.PNG ./Images/Geografico/geografico_500_KruskalI.png

Árbol de Expansión Mínima(KruskalI)

./Images/Geografico/MST_Geografico500_Prim_Costo.PNG ./Images/Geografico/geografico_500_Prim.png

Modelo Barabasi

30 nodos y grado 10

./Images/Babarasi/Babarasi_30.png

Árbol de Expansión Mínima(KruskalD)

./Images/Babarasi/MST_Babarasi30_KruskalD_Costo.PNG ./Images/Babarasi/Babarasi_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Babarasi/MST_Babarasi30_KruskalI_Costo.PNG ./Images/Babarasi/Babarasi_30_KruskalI.png

Árbol de Expansión Mínima(Prim)

./Images/Babarasi/MST_Babarasi30_Prim_Costo.PNG] ./Images/Babarasi/Babarasi_30_Prim.png

500 nodos y grado 12

./Images/Babarasi/Babarasi_500.png

Árbol de Expansión Mínima(KruskalD)

./Images/Babarasi/MST_Babarasi500_KruskalD_Costo.PNG ./Images/Babarasi/Babarasi_500_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Babarasi/MST_Babarasi500_KruskalI_Costo.PNG ./Images/Babarasi/Babarasi_500_KruskalI.png

Árbol de Expansión Mínima(KruskalI)

./Images/Babarasi/MST_Babarasi500_Prim_Costo.PNG] ./Images/Babarasi/Babarasi_500_Prim.png

Modelo Dorogovtsev

30 nodos

./Images/Dogorostev/Dogorostev_30.png

Árbol de Expansión Mínima(KruskalD)

./Images/Dogorostev/MST_Dogorostev30_KruskalD_Costo.PNG ./Images/Dogorostev/Dogorostev_30_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Dogorostev/MST_Dogorostev30_KruskalI_Costo.PNG ./Images/Dogorostev/Dogorostev_30_KruskalI.png

Árbol de Expansión Mínima(KruskalD)

./Images/Dogorostev/MST_Dogorostev30_Prim_Costo.PNG ./Images/Dogorostev/Dogorostev_30_Prim.png

500 nodos

Árbol de Expansión Mínima(KruskalD)

./Images/Dogorostev/MST_Dogorostev500_KruskalD_Costo.PNG ./Images/Dogorostev/Dogorostev_500_KruskalD.png

Árbol de Expansión Mínima(KruskalI)

./Images/Dogorostev/MST_Dogorostev500_KruskalI_Costo.PNG ./Images/Dogorostev/Dogorostev_500_KruskalI.png

Árbol de Expansión Mínima(KruskalD)

./Images/Dogorostev/MST_Dogorostev500_Prim_Costo.PNG ./Images/Dogorostev/Dogorostev_500_Prim.png