Aplicaciones de los algoritmos de Kruskal y Prim.

Question

¿Alguien podría dar algunas aplicaciones de los dos algoritmos, dónde y para qué aplicaciones pueden usarse?

Answer 1

Primero se estudiaron los árboles de expansión mínimo para obtener formas de establecer redes eléctricas de una manera que minimice el costo total del cableado. En un árbol de expansión mínimo, todos los nodos (casas) estarían conectados a la potencia por cables de una manera que tenga un costo y redundancia mínimo (cortar cualquier cable necesariamente corta la cuadrícula de energía en dos piezas).

Desde entonces, el problema ha sido bien estudiado y a menudo se usa como subrutina en algoritmos más complejos. los Algoritmo de Christofides Para encontrar soluciones aproximadas al problema del vendedor ambulante lo usa en un paso clave, al igual que algunos algoritmos para encontrar árboles Steiner.

Los árboles mínimos de expansión también se han utilizado para generar laberintos. Tanto el algoritmo de Kruskal como Prime se han utilizado de esta manera, a menudo creando laberintos de alta calidad.

Si está interesado en una historia completa del problema mínimo de los árboles de expansión, sus aplicaciones y sus algoritmos, hay un artículo realmente excelente disponible aquí Eso cubre todo esto. ¡Sugeriría encarecidamente darle una lectura!

¡Espero que esto ayude!

Answer 2

Citando a Wikipedia:

Un ejemplo sería una compañía de televisión por cable que coloca un cable 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 sea enterrado más profundo; Estos caminos estarían representados por bordes con pesos más grandes. Un árbol de expansión para ese gráfico sería un subconjunto de esos caminos que no tienen ciclos pero que aún se conecta a cada casa. 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

Primero debe comprender que el algoritmo de Prim y Kruskal es útil para encontrar Árbol de expansión mínimo en un gráfico. Una de las aplicaciones praticas del árbol de expansión mínima, se me ocurre es conectar diferentes oficinas de la misma compañía con menor costo.

Answer 4

• Topología
• Cartografía
• Geometría
• Agrupación
• Algoritmos de enrutamiento
• Generación de laberintos
• Redes mecánicas / eléctricas / informáticas
• Estudio de enlaces moleculares en química

Answer 5

Las aplicaciones de los algoritmos de Kruskal y Prims a menudo aparecen en las redes de computadora. Por ejemplo, si tiene una LAN grande con muchos interruptores, encontrar un árbol de expansión mínimo será vital para garantizar que solo se transmitirá un número mínimo de paquetes a través de la red.