Arbol DE Expansion Minima PDF

Preview

Summary

Arbol de expansión mínima...

Description

ARBOL DE EXPANSION MINIMA CONCEPTOS CLAVE • Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran orientados hacia afuera. • Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él. • Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo.

DEFINICION.- ARBOL DE EXPANSION • Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir una ruta entre cada par de vértices.

ARBOL DE EXPANSION MINIMA • El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bien representar una distancia o unidad de medida). • En pocas palabras, Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.

Solución «ALGORITMO DE PRIM»

1)

SOLUCIONAR:

UNA POTIBILIZADORA DE AGUA DE PACORA REQUIERE SUMINISTRAR AGUA A VARIOS CORREGIMIENTOS DEL ESTE DE MEXICO. EN EL SIGUIENTE GRAFICO SE MUESTRA LAS DIFERENTES ESTACIONES A DONDE DEBE SUMINISTRAR AGUA. DETERMINAR LA FORMA MAS ECONOMICA DE SUMINISTRAR AGUA A TODOS LOS CORREGIMIENTOS A TRAVES DE UN ARBOL DE EXPANSION MINIMA.

SOLUCION:

Solución «ALGORITMO DE KRUSKAL» ¿Qué es método de Kruskal?  Es un algoritmo de recubrimiento mínimo conexo ponderado, en pocas palabras, que va uniendo todos los nodos formando un árbol, tomando la arista que se va a empezar con el nodo de la menor unidad. Los pasos para realizar este método son los siguientes:  Comenzar en forma arbitraria en cualquier nodo y conectarlo con el más próximo tomando en cuenta de que el primer nodo sea el mínimo.  Identificar el nodo no conectado que este más cercano o menor de algunos de los nodos conectados. Deshacer los empates de forma arbitraria, de tal manera que no se cierren ciclos para continuar con el árbol.  Repetir el caso 2 hasta que se hayan conectado todos los nodos.

A continuación se presenta un ejemplo claro del

método de Kruskal

Y de esta manera podemos observar que mediante el método de Kruskal nos ayuda a encontrar una solución mínima que es la más óptima durante un problema de algún tipo de red.

REFERENCIAS: https://jariasf.wordpress.com/2012/04/19/arbolde-expansion-minima-algoritmo-de-kruskal/ https://es.slideshare.net/adncstell/53-arbolexpansin-minima-algoritmo-de-kruskal? next_slideshow=1 https://karenbandala.wordpress.com/about/2-3problema-arbol-expandido-minimo/

INTEGRANTES:  FRANCISCO SALATIEL FIGUEROA VAZQUEZ  ALAM OSVALDO FRUTOS GODINEZ



MARCO SANCHEZ GONZALEZ...