Arbol de costo_minimo
-
Upload
frank-resurrection -
Category
Documents
-
view
464 -
download
0
Transcript of Arbol de costo_minimo
ESCUELA SUPERIOR
POLITÉCNICA DE CHIMBORAZO
FACULTAD DE
INFORMÁTICA Y ELECTRÓNICA
ESCUELA DE TELECOMUNICACIONES
Y REDES
INVESTIGACION OPERATIVA
TEMA:
ÁRBOL DE COSTO MÍNIMO
OBJETIVOS GENERAL:
• Investigar acerca del tema árbol de costomínimo y los algoritmos que pueden darsolución a este problema.
OBJETIVOS ESPECIFICOS:
• Conocer los conceptos básicos acerca de grafos y del árbol de costo mínimo.
• Diferenciar los algoritmos de árbol de costo mínimo y ejemplos de cada uno, para tener una mejor comprensión del tema.
• Dar a conocer las aplicaciones que tienen el árbol de costo mínimo en nuestra vida diaria.
ÁRBOL DE COBERTURA MÍNIMO
• GRAFOS
Es una estructura que se puede
representar gráficamente la cual
permite interrelacionar elementos
dentro de un sistema.
Está formado por un conjunto de
elementos denominados nodos o
vértices y un conjunto de aristas o
arcos que permiten la unión entre
vértices
• Notación
Los grafos suelen utilizar la notación:
G=(V,A)
Donde:
V es el conjunto de vértices
A es el conjunto de aristas
• Utilidad
Los grafos sirven para representar de
manera grafica a las relaciones entre
un grupo de elementos comunes,
por ejemplo:
La distancia entre elementos
Representar redes de computadoras
Tipos de grafos
• Grafos dirigidos • Grafos no dirigidos
Grafos no dirigidos
• Son aquellos grafos cuyas aristas no tienen una
dirección definida, en este caso podemos observar
que la unión entre los vértices está dada únicamente
por aristas en las cuales el flujo puede tomarse según
nuestra facilidad para analizar el camino o recorrido
que toma.
• Es lo mismo decir la arista A-B que la arista B-A,
citando como caso particular.
ÁRBOLES
Definición
Es una estructura de datos que
puede ser representada gráficamente,
que está compuesta por dos
conjuntos similares a los estudiados
en grafos, es decir, presenta vértices
y aristas.
Características
• Se distingue un único nodo
en el cual inicia el árbol, el
cual es llamado nodo raíz,
éste nodo es padre de los
nodos que le siguen y están
conectados a él, y a su vez
estos nodos son padres de
los nodos que les siguen, así
de forma sucesiva.
• Los nodos resultantes o de
inferior rango se denominan
nodos hijos.
• Los últimos nodos se
denominan nodos hojas
• Los árboles poseen en cada nodo un nombre quelo identifica del resto y cada arista puede tenerun valor representativo de algún tipo demagnitud.
• Esta forma de analizar los árboles, nos permiteutilizarlos para diferentes fines, sin embargo sonutilizados frecuentemente para representarestructuras jerárquicas.
Organigrama de una empresaEstructuras de redes
Clasificación
• Árboles dirigidos
• Árboles binarios
• Árboles B
• Árboles rojo negro
• Árboles no dirigidos
De forma análoga a los grafos
no dirigidos, los arboles no
dirigidos se caracterizan por
no tener una dirección en sus
aristas lo que permite que el
flujo se lo realice en cualquier
dirección.
Esto implica que cualquier
nodo puede asumir el rol de
raiz
• Dado un grafo no dirigido, un árbol de cobertura mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial.
• Cada arista tiene asignado un peso, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol de cobertura mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión.
• Un árbol de cobertura mínima es un árbol recubridor que pesa menos o igual que otros árboles recubridores.
Problema árbol de cobertura mínima
• Este problema surge de la necesidad de
encontrar dentro de un grafo no dirigido, un
árbol que recorra todos los nodos del grafo, y
cuya suma de los peso o valores de las aristas
sea menor entre todos los arboles que se
puedan formar en el grafo en cuestión.
• El árbol resultante es el llamado:
“Árbol de cobertura mínima”
Ejemplo del problema
• Podemos encontrar dentro del grafo, el árbol de
cobertura mínima, puesto que observamos que el
numero de arboles que se pueden generar es
significativo.
ALGORITMO DE PRIM
• El algoritmo de Prim es un algoritmo
perteneciente a la teoría de los grafos para
encontrar un árbol de cobertura mínimo dentro
de un grafo no dirigido.
• En otras palabras, el algoritmo encuentra un
subconjunto de aristas que forman un árbol con
todos los vértices, donde el peso total de todas
las aristas en el árbol es el mínimo posible.
Ejercicio:
• Primero elegimos un nodo que
tomara la función de nodo raíz y
lo señalamos
• Luego se encuentran las aristas
que estén conectadas al nodo raíz
• De las aristas encontradas se
procede a determinar cual es la
que tiene menor peso y se la
señala.
• En el caso de encontrarse con
aristas que tengan el mismo peso
se procede a seleccionar una de
ellas de forma aleatoria.
• Se procede a marcar el nodo al
cual se encuentra conectada la
arista anteriormente seleccionada.
• Luego se vuelve a comparar los
pesos entre los nodos
relacionados, en este caso A-C,
como los pesos son iguales se
puede escoger cualquier arista.
• Se vuelve a marcar el nodo que
resulto estar conectada a la arista y
se repite de forma continua los
mismos pasos asta tener un árbol
que una todos los vértices.
• Finalmente podemos observar que todos los nodos están unidos, es
decir, el árbol de cobertura mínimo para el nodo raíz A, esta dado por la
siguiente figura:
ALGORITMO DE KRUSKAL
• De igual forma el algoritmo de kruskal es un
algoritmo de la teoría de grafos, que es utilizado para
encontrar el árbol de cobertura mínimo dentro de un
grafo determinado.
• 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.
Ejercicio:
• Se tiene un grafo inicial del cual
partimos:
• Primero procedemos a
determinar de entre todos las
aristas, cuál es la arista que tiene el
menor peso y la seleccionamos
• Procedemos a señalar la arista y
los vértices que une tomando en
cuenta lo explicado anteriormente.
• Realizamos el mismo
procedimiento, encontramos el
valor menor de los pesos y
marcamos los vértices que una
dicha arista.
• Se debe tomar en cuenta que lo
que se desea es encontrar un
árbol, es decir, que no deben
existir recorridos cerrados.
• Podemos observar que el siguiente
valor de arista a tomar debe ser el
número 3, pero en ese caso
estaríamos generando un
recorrido cerrado así que
tomamos el siguiente valor que en
este caso será el 4.
• Si podemos observar, se vuelve a
generar el inconveniente anterior
así que elegimos el valor que le
sigue.
• En el caso de que el valor que le
siga se repita, se puede escoger
cualquiera de las dos aristas,
tomando en cuanta que no se
debe generar un lazo cerrado.
• En la grafica se puede observar
que las dos aristas coinciden en un
punto, pero es necesario aclarar
que no se genera un lazo cerrado
ya que solo son trayectorias que
están pasando por un lugar en
común más no están en ningún
momento en intersección.
• El árbol expandido que se genera
es el siguiente:
APLICACIONES COBERTURA MÍNIMA
• La aplicación de estos problemas de
optimización dentro de nuestra especialidad y
nuestro diario vivir se ubica en las redes de
comunicación eléctrica, telefónica, carretera
ferrovía, aérea, marítima, etc., donde los nodos
representan puntos de consumo eléctrico,
teléfonos, aeropuertos, computadoras, y las
aristas podrían ser de alta tensión, cable de
fibra óptica, rutas aéreas, etc.
GRACIAS
POR SU ATENCIÓN
Por:
Marilin Carrión Ángel Ortega
Jhonattan Illapa Iván Armijo
Cristian Jacho Alex Yautibug
Franklin López John Tene
Cristian Colala Alex Segura
Jairo Arce