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)

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

500 nodos(50x10)

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

Modelo de Erdos y Renyi

30 Nodos y 200 Aristas

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

500 Nodos y 2500 Aristas

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

Modelo de Gilbert

30 nodos y probabilidad 0.5

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

500 nodos y probabilidad 0.02

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

Modelo Geográfico

30 nodos y distancia 0.5

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

500 nodos y distancia 0.15

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

Modelo Barabasi

30 nodos y grado 10

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

]

500 nodos y grado 12

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

]

Modelo Dorogovtsev

30 nodos

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz

500 nodos

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

• Archivo Graphviz

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

• Archivo Graphviz

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

• Archivo Graphviz