Aplicaciones de Kruskal y algoritmos de Prim

Question

Podría alguien por favor dar algunas aplicaciones de los dos algoritmos, dónde y qué aplicaciones pueden ser utilizados para?

Answer 1

árboles de expansión mínimos fueron estudiados por primera maneras para diseñar las redes eléctricas de una manera que minimice el costo total de la instalación eléctrica. En un árbol de expansión mínimo, todos los nodos (casas) estarían conectados a la alimentación por cables de una manera que tiene un costo mínimo y redundancia (cortar cualquier cable necesariamente corta la red eléctrica en dos partes).

Desde entonces, el problema ha sido bien estudiada y se utiliza a menudo como una subrutina en algoritmos más complejos. El Christofides algorithm para encontrar soluciones aproximadas al Problema de Vendedor Viajero lo usa en un paso clave, al igual que algunos algoritmos para encontrar árboles Steiner.

árboles de expansión mínima también se han utilizado para generate mazes. Tanto el algoritmo de Kruskal como el de Prim se han usado de esta manera, a menudo creando laberintos de alta calidad.

Si usted está interesado en una historia completa del problema del árbol de expansión mínimo, sus aplicaciones y sus algoritmos, hay una verdaderamente excelente papel available here que cubre todos estos. ¡Le sugiero que lo lea!

Espero que esto ayude!

Answer 2

Citando a Wikipedia:

Un ejemplo sería una empresa de televisión por cable de tendido de cables a un nuevo vecindario. Si se limita a enterrar el cable solo a lo largo de ciertas rutas, entonces habría un gráfico que representa qué puntos están conectados por esas rutas. Algunos de esos caminos pueden ser más caros, porque son más largos o requieren que el cable esté más enterrado; estos caminos estarían representados por bordes con pesos mayores. Un árbol de expansión para ese gráfico sería un subconjunto de los caminos que no tiene ciclos pero que aún se conecta a todas las casas. Puede haber varios árboles de expansión posibles. Un árbol de expansión mínimo sería uno con el costo total más bajo.

Fuente: http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 3

En primer lugar hay que entender que tanto el algoritmo de Kruskal de Prim y son útiles para encontrar Minimum spanning Tree en un gráfico. Una de las aplicaciones prácticas del árbol de expansión mínimo, en lo que puedo pensar es conectar diferentes oficinas de la misma empresa con el menor costo.

Answer 4

• topología
• Cartografía
• Geometría
• La agrupación
• enrutamiento Algoritmos
• Generación de laberintos
• mecánico/eléctrico/Computer Networks
• Estudio de enlaces moleculares en Química

Answer 5

Aplicaciones de Kruskal y algoritmos de Prim a menudo surgen en las redes de computadoras. Por ejemplo, si tiene una LAN grande con muchos conmutadores, encontrar un árbol de expansión mínimo será vital para garantizar que solo se transmita un número mínimo de paquetes a través de la red.