Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ALGORITMO DE KRUSKAL

No description
by

Alexis Jimenez Valdes

on 15 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ALGORITMO DE KRUSKAL

ALGORITMO DE KRUSKAL
ALGORITMO DE KRUSKAL
Este algoritmo fue escrito por Joseph Kruskal y publicado en 1956, es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.
Dado un grafo conexo, no dirigido G. 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.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo.

OBJETIVOS
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos
ESTE ALGORITMO ENCUENTRA EL ÁRBOL ABARCADOR DE COSTO MÍMINO DE UNA GRÁFICA G DE n VÉRTICES
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ
CARRERA: LIC. EN INGENIERÍA EN SISTEMAS Y COMPUTACIÓN
ASIGNATURA: ESTRUCTURA DE DATOS II
INTEGRANTES: ALEXIS F. JIMÉNEZ
JONATHAN CEBALLOS
ALAIN GARCÍA
LUIS ROUX
A CONSIDERACIÓN: PROFESORA: GABRIELA I. CABALLERO DE HISLOP
JOSEPH KRUSKAL
Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010)1 fue un matemático y estadístico estadounidense. Fue investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
ÁRBOL DE EXPANSIÓN
El grafo dado posee 3 arboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.
ÁRBOL DE EXPANSIÓN MINIMA
Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso.
El problema de hallar el Árbol de Expansión Mínima (minimum spanning tree MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal el cual investigamos este caso ambos usan técnicas voraces (greedy).
Un algoritmo voraz es aquel para resolver un determinado problema, sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Normalmente se aplica a los problemas de optimización.
El árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.
1. Repetir mientras existan vértices en P que se encuentren en particiones distintas
1.1. Seleccionar la arista(u,v) de menor costo
1.2 Si la arista conecta dos vértices que se encuentran en particiones diferentes
entonces Unir las particiones a las cuales pertenecen u y v.
2. Fin

APLICACIONES DEL ALGORITMO: DISEÑO DE REDES TELEFÓNICAS
Full transcript