Scribd
Cargar
185 vistas4 páginas

Árbol Mínima Recorrido

Este documento describe tres algoritmos para resolver el problema del árbol de expansión mínima: el algoritmo de Kruskal, que selecciona los arcos de menor longitud de forma incremental; el algoritmo de Prim, que encuentra el árbol de expansión mínima conecto y no dirigido; y el algoritmo de expansión mínima, que conecta de forma iterativa los nodos más cercanos no conectados. Además, presenta tres ejercicios para aplicar estos algoritmos a problemas de suministro de agua, cableado y oleoductos.

Cargado por

Maria Larreta
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
185 vistas4 páginas

Árbol Mínima Recorrido

Este documento describe tres algoritmos para resolver el problema del árbol de expansión mínima: el algoritmo de Kruskal, que selecciona los arcos de menor longitud de forma incremental; el algoritmo de Prim, que encuentra el árbol de expansión mínima conecto y no dirigido; y el algoritmo de expansión mínima, que conecta de forma iterativa los nodos más cercanos no conectados. Además, presenta tres ejercicios para aplicar estos algoritmos a problemas de suministro de agua, cableado y oleoductos.

Cargado por

Maria Larreta
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

PROBLEMA DEL ÁRBOL DEL MÍNIMO RECORRIDO

Existen tres métodos:

 Algoritmo Krustal
 Algoritmo Prim
 Algoritmo Expansión Mínima

Algoritmo Krustal

1.- Comience seleccionando el arco de menor longitud

2.- En cada interacción agregue el siguiente arco de menor longitud del conjunto
de arcos disponibles

3.- El algoritmo finaliza cuando todos los arcos estén conectados. (Si N = # de
nodos, entonces la solución óptima debe incluir n – 1 arcos).

Algoritmo Prim

Consiste en encontrar el árbol de expansión mínima que tiene cierto grado, que
debe ser:

 Conexo
 No dirigido
 Vértices etiquetadas
 Ponderar las aritas

Algoritmo Expansión Mínima

1.- Construir una tabla representando en filas y columnas los nodos de la red.
Cada celda se completa con la distancia entre los nodos.

2.- Se selecciona de manera arbitraria, cualquier nodo y se conecta, es decir, se


agrega una ligadura al nodo distinto más cercano.

3.- Se identifica el nodo no conectado más cercano a un nodo conectado y se


conectan estos dos nodos, esto es, se agrega una ligadura entre ellos.

4.- Si hay empate se elige se selecciona uno arbitrariamente, esto significa que
existe más de una solución óptima.
EJERCICIOS
1).-Interagua requiere suministrar agua a varios corregimientos del este de la
ciudad de Guayaquil. En el siguiente gráfico se presenta los diferentes puntos
donde debe dar el abastecimiento.

Desarrolle este problema de forma breve y concisa de cómo determinar la forma


más económica de suministrar agua a todos los corregimientos utilizando el
algoritmo de Krustal.
2).- La Empresa “Claro TV” va a proporcionar servicio de cable a cinco desarrollos
habitacionales. En la siguiente ilustración muestra las posibles conexiones de TV a las
cinco áreas, con las millas de cable anexadas a cada arco. El objetivo es determinar la red
de cables más económica, utilizando el algoritmo de Prim y definir la cantidad de millas
mínima de recorrido.
3).- La siguiente ilustración de problema del árbol del mínimo recorrido da la distancia en
millas de los vínculos factibles que conectan nueve cabezales de pozos de gas natural
localizados a una cierta distancia de la costa con un punto de distribución costero. Como
el cabezal del pozo 1 es el más cercano a la costa, dispone de una suficiente capacidad de
bombeo y almacenamiento para bombear la producción de los ochos pozos restantes al
punto de distribución.

Determine la red de oleoductos mínima que vincule los cabezales de los pozos al punto de
distribución.

También podría gustarte