generalidades de las redes
TRANSCRIPT
Operativa IIMODELO DE REDES
FRANCISCO VARGASINGENIERO DE SISTEMAS
ESPECIALISTA EN GERENCIA DE SISTEMAS INFORMÁTICOSMAGÍSTER EN CIENCIAS DE LA INFORMACIÓN Y LAS COMUNICACIONES CON ÉNFASIS EN
TELEINFORMÁTICACANDIDATO A DOCTOR EN CIENCIA Y TECNOLOGÍA INFORMÁTICA
2015
MODELO DE REDES
Problemas de transporte ( o distribución)
Envío de mercancías entre fuentes y destinos
0. GENERALIDADES
Con costos de transporte mínimo
Modelo de red
Se representa y resuelve
Ejemplos:a. Diseño red de tubería de gas natural, conectar fuentes del Golfo de México con
un punto de entrega en tierra objetivo minimizar el costo de construcción del conducto.
b. Determinación de la ruta más corta que une 2 ciudades en una red de caminos existente
c. Determinación del programa de flujo de costo mínimo de los campos petrolíferos a refinerías , y finalmente a centros de distribución. Se puede enviar petróleo y derivados en buques, oleoductos y/o camiones.Conclusiones: Los problemas de optimización de redes se pueden
representar en términos generales a través de uno de cuatro modelos:1. Modelo del árbol de extensión mínima 2. Modelo de la ruta más corta3. Modelo del flujo máximo 4. Modelo de red capacitada de costo mínimo
MODELO DE REDES
1. DEFINICIÓN DE REDES
RED Nodo 1Nodo 2
Nodo n
.
.
.
Arcos o ramas
Ejemplo: Red de transporte
Notación: Red GG = (N, A), donde N es el conjunto de nodos y A es el conjunto de ramas
3
2 4
5
1
Figura 1.
La red de la figura se describe así:5 nodos, 8 ramas
N= 1,2,3,4,5A= (1,3), (1,2), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)
MODELO DE REDES
1. DEFINICIÓN DE REDES
• El flujo de una rama está limitado por su capacidad que puede ser finita o infinita• Rama dirigida u orientada: Si permite un flujo positivo en una dirección, y
cero flujo en la dirección opuesta.• Red dirigida: Red con todas sus ramas dirigidas.• Trayectoria: Es una secuencia de ramas distintas que conectan 2 nodos sin
considerar la orientación de las ramas individuales. Por ejemplo: en la figura 1 las ramas (1,3), (3,2), y (2,4) constituyen una trayectoria del nodo 1 al 4.• Una trayectoria forma un lazo o ciclo si conecta un nodo consigo mismo. Por ejp
en la figura 1 las ramas (2,3), (3,4), y (4,2) forman un lazo.• Lazo dirigido o circuito es un lazo donde todas las ramas tienen la misma
dirección u orientación.• Red conectada, Es una red donde cada dos nodos distintos están conectados por
una trayectoria como se observa en la figura 1.• Árbol: Es una red conectada que puede constar solo de un subconjunto de los
nodos.• Árbol extenso: Es una red conectada que incluye todos los nodos de la red sin
lazos.3
2
1
4
3
2
1
4
5
Árbol extenso
Árbol