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
de flujo máximo. Siendo G una red de trasporte, 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 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
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.
No hay comentarios:
Publicar un comentario