3.8 REDES

3.8.1 MODELOS DE REDES:

Empezaremos por definir lo que es una red de transporte y cómo se utilizan para modelar.

DEFINICION 1. Una Red de Transporte R es un grafo dirigido ponderado con las siguientes características:

I.) Tiene un nodo fijo F, llamado fuente, el cual no tiene ninguna arista terminal.

II.) El peso de cada arista (i,j) es no negativo; esto es, w(i,j) ≥ 0.

DEFINICION 2. Sea R una red de transporte con fuente F y sumidero S y con pesos w(i,j) para cada arista (i,j). Un flujo en R es una función f que asigna a cada arista (i,j) un número (i,j) tal que

I.) f(i,j) ≤ w(i,j).

II.) Para toda j ≠ F, S tenemos que: ∑f(i,j) = ∑f(j,i)

el lado izquierdo de la igualdad se llama flujo de entrada y el de la derecha el de salida del nodo j. VER IMAGEN

Las redes de transporte tienen algunas propiedades que son inmediatas, una de ellas que reulta muy importante es el hecho de que el flujo de salida de la fuente es igual al flujo de enetrada del sumidero. Esto se puede establecer en el teorema siguiente utilizando la simbología apropiada.

TEOREMA. Sea R una red de transporte con flujo f, entonces: ∑f(F,i) = ∑f(i,S)

EJEMPLO. En una parte de la ciudad se van a colocar dos bombas de agua para abastecer a tres colonias de acuerdo al siguiente diagrama: VER EJEMPLO

Como se puede ver, esta no es una red de transporte puesto que no hay una fuente ni un sumidero. Pero debido a que es un grafe dirigido y que el “flujo” va de izquierda a derecha podemos fácilmente convertirla en una red, agregándole un nodo fuente F y otro nodo sumidero S.

Para esto, le agregamos las correspondientes aristas con ∞ como peso, para dar opción a cualquier posible valor. VER IMAGEN

BIBLIOGRAFIA:

I.) Matemáticas para computadora de Luis Alberto Lomeli Beherendt

---------------------------------------------------------------------------------------------------