Definiciones para redes

4.2.1. Terminología.

Definiciones para redes.

• Una red consiste en una serie de Nodos enlazados con 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.

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

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

• Con cada red se asocia algún tipo de flujo, ejemplo: flujo de productos petroleros en un oleoducto y flujos de tráfico de automóviles en carreteras.

• 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.

• Un ciclo es dirigido si consiste en una ruta dirigida.

• Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta.

• Un árbol es una red conectada que puede consistir solo en un subconjunto de todos los nodos en ella donde no se permiten ciclos.

• Árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos.

• Una trayectoria es una secuencia de ramas distintas que conectan dos nodos sin considerar la orientación de las ramas individuales.

Ejemplo:

1.-) Para cada red de la figura siguiente, determine:

a) una ruta.

b) un ciclo.

c) un ciclo dirigido.

d) un árbol.

e) un árbol de expansión.

f) determine los conjuntos N y A.

Soluciones:

a) Ruta:

b) Ciclo: (1,3,4,2,1)

c) Ciclo dirigido: (1,3,4,5,1)

d) Árbol:

e) Árbol de extensión:

f) Conjuntos N y A.

N = (1, 2, 3, 4, 5)

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

4.2.2. Construcción de una red.

Para aplicar CPM y PERT, se necesita una lista de actividades que conformen el producto. Se considera que el proyecto está completo cuando se terminan todas las actividades. Para cada actividad, hay un conjunto de actividades (llamadas predecesores de la actividad) que deben completarse antes que comience la actividad. Un proyecto de red se utiliza para representar las relaciones de precedencia entre actividades. En este análisis, las actividades se representan por actos directos, y los nodos se utilizan para representar la terminación de un conjunto de actividades. (Por esta razón, a menudo se hace referencia a los nodos del proyecto como eventos). Este tipo de red de proyecto se llama red AOA (por sus siglas en inglés actividad en arco).

Para entender cómo una red AOA representa relaciones de precedencia, suponga que la actividad A es un predecesor de la actividad B. cada nodo en una red AOA representa la terminación de una o más actividades. Así, el nodo 2 de la figura 1 representa la terminación de la actividad A y el comienzo de la actividad B. suponga que las actividades A y B se deben completar antes que empiece la actividad C. en la figura 2,

...