clase8 2

Modelos de Redes: Árbol
de expansión mínima
M. En C. Eduardo Bustos Farías

Objetivos




Conceptos y definiciones de redes.
Importancia de los modelos de redes
Modelos de programación lineal, representación en
redes y soluciones usando el computador para:

* Modelos de asignación
* Modelo del vendedor viajero
* Modelos de la ruta mas corta
* Modelos de la rama mas corta
Y otros.

6

8

Unproblema de redes es aquel que puede
representarse por:

10

9

7

Nodos

10

Arcos

Funciones en los arcos

Introducción


La importancia de los modelos de redes:
* Muchos problemas comerciales pueden ser resueltos a través
de modelos redes
* El resultado de un problema de redes garantiza una solución
entera, dada su estructura matemática. No se necesitan
restricciones adicionales para obtenereste tipo de solución.
* Problemas de redes pueden ser resueltos por pequeños
algoritmos , no importando el tamaño del problema, dada su
estructura matemática.



Terminología de Redes
* Flujo: Corresponde a la cantidad que debe transportarse
desde un nodo i a un nodo j a través de un arco que los
conecta. La siguiente notación es usada:

Xij= cantidad de flujo
Uij= cota mínima de flujo que sedebe transportar
Lij= cota maxíma de flujo que se puede transportar.
* Arcos dirigidos /no dirigidos: Cuando el flujo puede
transportarse en una sola dirección se tiene un arco dirigido (la
flecha indica la dirección). Si el flujo puede transportarse en
ambas direcciones existe un arco no dirigido (sin flecha).
* Nodos adyacentes: Un nodo j es adyacente con un nodo i si
existe un arco que une elnodo j con el nodo i.



Rutas/Conexión entre nodos
*Ruta: Una colección de arcos formados por una serie de
nodos adyacentes
* Los nodos están conectados si existe una ruta entre ellos.



Ciclos / Arboles /Arboles expandidos
* Ciclos : Un ciclo se produce cuando al partir de un nodo por
un cierto camino se vuelve al mismo nodo por otra ruta.
* Arbol : Una serie de nodos que no contienen ciclos.*Arbol expandido: Es un árbol que conecta todos lo nodos de
la red (contiene n-1 arcos).

Árbol de expansión mínima

7

Árbol de expansión mínima


Este problema surge cuando todos los nodos de una
red deben conectar entre ellos, sin formar un loop.



El árbol de expansión mínima es apropiado para
problemas en los cuales la redundancia es
expansiva, o el flujo a lo largo de los arcos seconsidera instantáneo.

8

Árbol de expansión mínima
¾

¾

¾
¾

Este problema se refiere a utilizar las ramas o arcos de
la red para llegar a todos los nodos de la red, de manera
tal que se minimiza la longitud total.
La aplicación de estos problemas de optimización se
ubica en las redes de comunicación eléctrica, telefónica,
carretera, ferroviaria, aérea, marítima, etc.; donde los
nodos representanpuntos de consumo eléctrico,
teléfonos, aeropuertos, computadoras.
Y los arcos podrían ser de alta tensión, cable de fibra
óptica, rutas aéreas, etc.
Si n = numero de nodos, entonces la solución óptima
debe incluir n-1 arcos.
9

Algoritmo de Kruskal

10

Algoritmo de Kruskal
1.

2.

3.

Comenzar en forma arbitraria en cualquier
nodo y conectarlo con el mas próximo (menos
distante o costoso).Identificar el nodo no conectado que esta más
cera o menos costoso de alguno de los nodos
conectados. Deshacer los empates de forma
arbitraria. Agregar este nodo al conjunto de
nodos conectado.
Repartir este aso hasta que se hayan
conectado todos los nodos.
11

EJEMPLO 1
EL TRANSITO DEL DISTRITO
METROPOLITANO
Árbol de expansión mínima

12

EL TRANSITO DEL DISTRITO
METROPOLITANO







La ciudadde Vancouver esta planificando el
desarrollo de una nueva línea en sistemas de
tránsito.
El sistema debe unir 8 residencias y centros
comerciales.
El distrito metropolitano de transito necesita
seleccionar un conjunto de líneas que conecten
todos los centros a un mínimo costo.
La red seleccionada debe permitir:
- Factibilidad de las líneas que deban ser construidas.
- Mínimo costo posible por...