6.5 REDES TEOREMA DE FLUJO MÁXIMO TEOREMA DE FLUJO MÍNIMO PAREOS Y REDES DE PETRI
Una Red de Transporte es una gráfica 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 número no negativo.
Teorema del flujo mínimo.
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedando 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); vV1, w? V2 V1es 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.
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 contienen 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.