Redes


Tecnológico Nacional de México
Instituto Tecnológico de Celaya
Ingeniería Industrial
Investigación de operaciones
M.C. Rosa Ma. Luna Ramos
Mayra Andrea Jaramillo Trejo


TERMINOLOGÍADefiniciones de red.
Una red se compone 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 dearcos.

Ejemplo: La siguiente red se describe como:


N= {1,2,3,4,5}

A={(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)


Asociado con cada red hay un flujo (por ejemplo, los productos depetróleo fluyen
por un oleoducto y el tráfico de automóviles fluye por las carreteras). 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 flujo positivo sólo 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 através de otros nodos en la red. En el ejemplo los arcos (1,2), (2,3), (3,4) y (4,5) forman una ruta entre los nodos 1 y 5. Una ruta forma un ciclo o un bucle si conecta un nodo de vuelta a sí mismo através de otros nodos. En la figura, los arcos (2,3), (3,4) y (4,2) forman un ciclo.


Se dice que una red está conectada si cada dos nodos distintos están conectados
en al menos una ruta. La red delejemplo muestra este tipo de red. Un árbol es una 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. Lasiguiente figura proporciona ejemplos de un árbol y un árbol de expansión de la red de la figura del ejemplo.








APLICACIÓN

Muchas situaciones de investigación de operaciones pueden modelarse yresolverse como redes (nodos conectados por ramas).

Los siguientes puntos son algunas aplicaciones

1. Diseño de una red de oleoductos para gas natural a una determinada distancia de la costa para...