Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes:
• Poseer una fuente o vértice fijo que no tiene aristas de entrada.
• Poseer un sumidero o vértice fijo que no tiene arista de salida
• El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” es un numero no negativo.

 

 

Ejemplo de una red que parte de un punto a que es un Muelle y llega a un punto z que es una refinería.



Teorema de flujo máximo.

Siendo G una red de trasporte, un flujo máximo es un flujo con valor máximo.
En general, habrá varias flujos con el mismo valor máximo.
La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa 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.

Teorema del flujo mínimo.

En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Se llama capacidad de un corte a la suma:

Capacidad (v,w) ; v Є V1 , w ЄV2

• V1 es la parte que contiene a la fuente

• V2 es la parte que contiene al sumidero

Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que  el valor de F; es decir:

i ЄP   JЄP Cij   i F ai



La notación  i : Significa la suma sobre todos los vértices i

Demostración: observe j ЄP   iЄP Cji = j ЄP   iЄP F ij

Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P

Ahora 

 i F ai= j ЄP  j Fji -j ЄP  j
=j ЄP  iЄP Fji +j ЄP  iЄP Fji- =j ЄP  iЄP Fji
=j ЄP  iЄP Fji -j ЄP  iЄP Fji- j ЄP  iЄP Fji j ЄP  iЄP Cji



El corte minimal nos da la minima capacidad del corte efectuado en el grafo.

Redes de Petri

Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados mediante circunferencias) y  transiciones (representadas por segmentos rectos verticales). Los  lugares y las transiciones se unen mediante arcos o flechas.

Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones.
Una transición puede ser destino de varios lugares y un lugar puede ser el destino de varias transiciones.
Una  transición puede ser  origen de  varios lugares y un lugar puede ser  origen de varias transiciones.
Los lugares pueden presentar marcas (una marca se representa mediante un punto en el interior del círculo).
Cada lugar tiene asociada una acción o salida.
Los lugares que contiene marcas se consideran lugares activos.
Cuando un lugar está activo sus salidas están a uno.
A las transiciones se les asocia eventos (funciones lógicas de las variables de entrada).
Una transición se dice que está sensibilizada cuando todos su lugares origen están marcados.

Cuando ocurre un evento asociado a una transición (la función lógica se hace uno), se dice que la transición está validada.!