Las redes

UNIVERSIDAD AUTONOMA DE TAMAULIPAS

FACULTAD DE INGENIERA “ARTURO NARRO SILLER”

INVESTIGACION DE OPERACIONES

UNIDAD 2

INTEGRANTES PARTICIPACION
CONTRERAS MARIÑO CARLOS ALFONSO………..100%
GAMEZ VASQUEZ JESUS FERNANDO……………….100%
GARZA ZAPIEN CARLOS JAVIER………………………..100%
SOTO FIGAROLA HECTOR………………………………..100%

Índice

II Redes
2.1Elementos de una Red
Una red se descompone de un conjunto de nodos unidos por arcos(o ramas). La notación para describir una red es (N, A) donde N es el conjunto de nodos, y A es el conjunto de arcos.
Asociado con una red hay un flujo, el flujo máximo en una red puede ser finito o infinito, según la capacidad de sus arcos.
Se dice que un arco está dirigido u orientado si permite el flujopositivo solo en una dirección. Una red dirigida tiene todos los arcos dirigidos.
Una ruta es un conjunto de arcos que unen dos nodos distintos, y que pasan a través de otro nodos en la red. Una ruta forma un ciclo o un bucle si conecta un nodo de vuelta a sí mismo a través de otros nodos.
Se dice que una red está conectada si cada dos nodos distintos están conectados en al menos una ruta. Un árbol esuna red conectada libre de ciclos compuesta de un subconjunto de todos los nodos y un árbol de expansión es un árbol que une todos los nodos de la red.
2.2 Ruta más Corta
Este problema determina la ruta más corta entre un origen y un destino en una red de transporte. Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda red a partirdel origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino. El mismo modelo puede representar otras situaciones.
Algoritmos de la ruta más corta
1.- El algoritmo de Dijkstra para determinar las rutas más cortas entre el nodo origen y losdemás nodos en la red.
2.- El algoritmo de Floyd para determinar la ruta más corta entre dos nodos cualesquiera en la red.
Algoritmo de Dijkstra
Sea ui la distancia más corta del nodo origen 1 al nodo i, y defina dij ( ≥ 0) como longitud del arco (i,j). El algoritmo define la etiqueta para un nodo j que sigue inmediatamente como
[uj,i] = [ui + dij,i],dij≥0
La etiqueta para el nodo de inicioes [0,2], que indica que el nodo no tiene predecesor. Las etiquetas de nodo en el algoritmo de Dijkstra son de dos tipos: temporales y permanentes. Una etiqueta temporal en un nodo se modifica si puede hallarse una ruta más corta al nodo. De lo contrario, el estado temporal cambia a permanente.
Algoritmo de Floyd
Este algoritmo es más general que el Dijkstra porque determina la distancia entrenodos cualesquiera en la red. El algoritmo representa una de n nodos como una matriz cuadrada con n filas y n columnas, la entrada (i,j) de la matriz da la distancia dij del nodo i al nodo j, la cual es finita si i está vinculado directamente a j, e infinita en caso contrario.
Ejercicio
1.- La red de la figura presenta las distancia en millas entre pared de ciudades 1,2,…,8. Use el algoritmo deDijkstra para determinar la ruta más corta entre la siguientes ciudades.
(a) Ciudades 1 y 8
(a) Ciudades 1 y 6
(a) Ciudades 4 y 8
(a) Ciudades 2 y 6

2.3 Árbol de Extensión Mínima
El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que ya sabemos. En ambos casos se considera una red no dirigida y conexa, en la quela información dada incluye alguna medida de longitud positiva asociada con cada ligadura.
Este problema se puede resumir como sigue:
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.
2.- Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de...