Modelo De Redes



Índice
Introducción…………………………………………………………………………………………………………………..……1
Técnica del árbol de expansión mínima……………………………………………………………………………….2
Algoritmo de kruskal…………………………………………………………………………………………………………….2.1
Técnicas del flujo máximo……………………………………………………………………………………………………3
Técnica de la ruta más corta…………………………………………………………………………………………………4
Ruta más cortateoría…………………………………………………………………………………………………………..4.1
Importancia…………………………………………………………………………………………………………………………..4.2
Ejemplos………………………………………………………………………………………………………………………………..4.3
Notación y terminología…………………………………………………………………………………………………………5
Conclusiones………………………………………………………………………………………………………………………….6














Tema: Modelo de Redes



Profesor: wilzer Rocha

Integrantes: Andia Fernández Katherine
Acuña Pérez angelo
Bautista valdiviezo Carla
Salvatierra ramos CinthiaSulca zuloaga Silvia
Razo Gutiérrez Raúl

2015




INTRODUCCION




Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de navegación de los cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos y todasaquellas situaciones que puedan representarse mediante una red donde los nodos representan las estaciones o las ciudades, los arcos los caminos, las líneas aéreas, los cables, las tuberías y el flujo lo representan los camiones, mensajes y fluidos que pasan por la red. Con el objetivo de encontrar la ruta más corta si es una red de caminos o enviar el máximo fluido si es una red de tuberías.
Cuando setrata de encontrar el camino más corto entre un origen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existen otros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo cada uno abarca un problema en particular. En este trabajo se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos,además se describen los algoritmos que aplican estos modelos para encontrar la solución óptima al problema. Utilizando la terminología utilizada para representarlos como una red.






























MODELOS DE REDES
Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:
Modelo de minimización de redes (Problema del árbolde mínima expansión).
Modelo de la ruta más corta.
Modelo del flujo máximo.
Modelo del flujo del costo mínimo.
Modelo de minimización de redes
El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se debenincluir ciclos en al solución del problema.
Para crear el árbol de expansión mínima tiene las siguientes características:
1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
2. Se deseadiseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal maneraque la red resultante formen un árbol de expansión. Por tanto el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.
Algoritmo para construir el árbol de expansión mínima:
1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo...