1
Redes
Peñaloza Tapia Ricardo
Ingeniería en Sistemas Computacionales, Instituto Tecnológico de Tláhuac
AEF-1041: Matemáticas Discretas
Padilla Salas Rodrigo Manuel
29 de abril de 2020
2
Redes
Modelo de Redes
Consideremos la gráfica mostrada, que representa una red de tuberías de
petróleo:
El petróleo se descarga en el muelle a y se bombea a través de la red
hasta la refinería z.
Los vértices b, c, d y e representan estaciones de bombeo intermedias.
Las aristas dirigidas representan las sub-tuberías del sistema y
muestran la dirección en que el petróleo puede fluir.
Las etiquetas sobre las aristas indican la capacidad de cada sub-
tubería.
Red de Transporte
Una red de transporte (o más simple, una red) es una gráfica dirigida, simple, con
pesos que satisface:
a) Un vértice fijo, la fuente denotada por a, no tiene aristas de entrada.
b) Un vértice fijo, el sumidero (o destino) denotada por z, no tiene aristas
de salida.
c) El peso Cij de la arista dirigida (i, j), llamado la capacidad de (i, j), es
un número no negativo.
3
Ejemplo:
La grafica es una red de transporte. La fuente es el vértice a y el sumidero es el
vértice z. La capacidad de la arista (a, b), Cab es 3, y la capacidad de la arista (b,
c), Cbc es 2.
Flujo de una Red
Un Flujo en una red asigna un flujo de una arista dirigida que no excede la
capacidad de dicha arista.
Definición:
Sea G una red de transporte. Sea Cij la capacidad de la arista dirigida (i, j). Un flujo
F en G asigna a cada arista dirigida (i, j) un número no negativo Fij tal que:
a) Fij <= Cij
b) Para cada vértice j, que no sea la fuente ni el sumidero, ∑Fij = ∑Fji
(Propiedad de la conservación del Flujo).
En esta suma a menos que se indique lo contrario, se supone que la suma se
realiza sobre todos los vértices i. Además si (i, j) no es una arista, hacemos Fij =
0.
Fij es el flujo de la arista (i, j). Para cualquier vértice j.
∑Fij es el flujo de entrada a j.
∑Fji es el flujo de salida de j.
4
Ejemplo 1:
Las asignaciones:
Fab = 2, Fbc = 2, Fcz = 3, Fad = 3, Fdc = 1, Fde = 2, Fez = 2, definen un flujo para
la red de la figura.
Por ejemplo, el flujo de entrada del vértice d, es Fad = 3, es igual al flujo de salida
del vértice d, Fdc + Fde = 1 + 2 = 3.
Una arista e se etiqueta “x, y” si la capacidad de e es x y el flujo en e es y.
En este ejemplo, el flujo de salida de la fuente a, Fab + Fad, es igual al flujo de
entrada del sumidero z, Fcz + Fez, ambos iguales a 5.
Teorema
Dado un flujo F en una red, el flujo de salida de la fuente a es igual al flujo de
entrada del sumidero z, es decir: ∑Fai = ∑Fiz
Valor del Flujo
Sea F un flujo en una red G. El valor ∑Fai = ∑Fiz es el valor del flujo F.
En el ejemplo anterior el valor del flujo en la red es de 5.
5
Ejemplo 2: Una red de Bombeo
La figura representa una red de bombeo por medio de la cual se envía agua a 2
ciudades, A y B, desde 3 pozos, W1, W2y W3.
Las capacidades de los sistemas intermedios aparecen sobre las aristas.
Los vértices b, c y d representan estaciones de bombeo intermedias.
Modelar este sistema como una red de transporte.
Para obtener una fuente y un sumidero fijos, podemos obtener una red de
transporte equivalente, uniendo las fuentes en una superfuente y los sumideros
en un supersumidero.
∞ representa una capacidad ilimitada.
Ejemplo 3: Una Red de Flujo de Trafico
Es posible ir de la ciudad A a la ciudad C directamente o pasar por la ciudad B.
Durante el periodo de 6:00 a 7:00 p.m., los tiempos promedios son:
A a B (15 minutos)
6
B a C (30 minutos)
A a C (30 minutos)
Las capacidades máximas de las carreteras son:
A a B (3000 carros)
B a C (2000 carros)
A a C (4000 carros)
Representar el flujo de tráfico de A a C, de 6:00 a 7:00 p.m. como una red.
Teorema Flujo MÁXIMO
Siendo G una red de transporte, un flujo máximo es un flujo con valor máximo.
En general, habrá varios flujos con el mismo valor máximo.
La idea es sencilla: “comenzar con cierto flujo inicial e incrementar de forma
iterativa (repetida) hasta que no pueda mejorarse más. El flujo resultante será el
máximo”.
Para aumentar el valor de un flujo dado, debemos determinar un camino de la
fuente al sumidero e incrementar el flujo a lo largo de ese camino.
Terminología
Se denotará a G como una red con fuente a, sumidero z y capacidad C.
Las aristas se tomarán como no dirigidas, por el momento, y sea:
P = (v0, v1,…, vn), v0 = a vn = z un camino de a a z de esta gráfica.
7
Si una arista e en P está dirigida de vi-1 a vi, decimos que e está orientada en
forma propia (con respecto a P), caso contrario, se dice que e esta orientada
en forma impropia (con respecto a P).
Aumento de Flujo en Orientación Propia
Solo se podrá hacer si al determinar un camino P de la fuente al sumidero, todas
las aristas están orientadas en forma propia, y el flujo en cada arista es menor que
la capacidad de esta.
Aumento de Flujo en Orientación Impropia
Sea P un camino de a a z, y x un vértice intermedio (que no sea ni a ni z) en P.
Existen cuatro posibilidades para las orientaciones de las aristas e1 y e2 incidentes
en x:
Caso A: La arista e1 está de forma impropia y e2 no. Si incrementamos en
∆ el flujo en e2, debemos disminuir en ∆ el flujo en e1, de modo que el flujo
de entrada siga siendo igual al flujo de salida.
8
Caso B: La arista e2 está de forma impropia y e1 no. Si incrementamos en
∆ el flujo en e1, debemos disminuir en ∆ el flujo en e2, de modo que el flujo
de entrada siga siendo igual al flujo de salida.
Caso C: Las dos aristas están en forma impropia. Ahora debemos
disminuir el flujo en ambas aristas en ∆.
Caso D: Las dos aristas están en forma propia. Si incremento el flujo en
ambas aristas en ∆, el flujo de entrada en x seguirá siendo igual al flujo de
salida en x.
Ejemplo:
Las aristas (a, b), (c, d) y (d, z) están en forma propia. La arista (c, b) esta
orientada en forma impropia.
Disminuimos el flujo en 1 en la arista impropia (c, b) y aumentamos el flujo en 1
en las aristas orientadas en forma propia (a, b), (c, d) y (d, z). El valor del nuevo
flujo es 1 más que el origina.
9
Teorema
Sea P un camino de a a z en una red G tal que:
1) Para cada arista (i, j) de P, orientada en forma propia Fij < Cij
2) Para cada arista (i, j) de P, orientada en forma impropia Fij > 0
Sea: ∆ = min X, donde X consta de los números Cij – Fij para las aristas (i, j) de P
orientadas en forma propia, y Fij para las aristas (i, j) de P orientadas en forma
impropia. Definimos:
Entonces F* es un flujo cuyo valor es ∆ unidades mayor que el valor de F.
