Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Figura 2.2.1. Ejemplo de una red (N,A)
Con cada red se asocia algún tipo de flujo (por ejemplo, flujo de productos petrolero en un
oleoducto y flujos de tráfico de automóviles en carreteras). En general, el flujo en una red está limitado
por la capacidad de sus arcos, que pueden ser finitos o infinitos.
Se dice que un arco es dirigido u orientado si permite un flujo positivo en una dirección, y flujo
cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos.
Una ruta es una sucesión de arcos distintos que unen dos nodos pasando por otros nodos,
independientemente de la dirección de flujo en cada arco. Una ruta forma un ciclo si conecta un nodo
consigo mismo, pasando por otros nodos. Por ejemplo, en la figura 2.2.1, los arcos (2,3), (3,5) y (5,2)
forman un bucle o circuito cerrado. Un ciclo es dirigido si consiste en una ruta dirigida, por ejemplo
(2,3), (3,4).y (4,2) en la figura anterior.
Una red conectada es aquella en que cada dos nadas distintos están enlazados al menos por una
ruta. La red de la figura 2.2.2 es un ejemplo de este tipo. Un árbol es una red conectada que puede
consistir sólo en un subconjunto de todos los nadas en ella, donde no se permiten ciclos, y un árbol de
expansión es un árbol que enlaza todos los nadas de la red, también sin permitir ciclos. En la figura
2.2.2. se ven ejemplos de un árbol y de un árbol de expansión para la red de la figura 2.2.1
FIGURA 2.2.2 Ejemplos de un árbol y de un árbol de expansión, para la red de la figura 2.2.1
Árbol
Árbol de expansión
6
6
Semana 6: Tarea de investigación: f) Realizar una investigación del uso y aplicación e los modelos de redes
42