REDES (Teorema del flujo máximo y mínimo; Redes de Petri y de Pareo)

 REDES:

Una red de transporte es una gráfica dirigida, simple, con pesos y que debe cumplir las siguientes condiciones:

1- Poseer una fuente o vértice fijo que no tiene aristas de entrada

2- Poseer un sumidero o vértice fijo que no tiene arista de salida

3- El peso Cij de la arista dirigida de i a j llamado capacidad de "ij" es  un número no negativo.

También: 

·     Un vértice fijo, designado como el origen o fuente, no tiene aristas de entrada.

·     Un vértice, designado como destino o sumidero, no tiene aristas salientes.

·     El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un número no negativo

 

TEOREMA DEL FLUJO MAXIMO:

se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo.

Una red de flujo es un grafo dirigido G= ( V, E) donde cada arco (u, v) perteneciente a E tiene la capacidad no negativa. S e distinguen dos nodos: la fuente o nodo s y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo a una fuente común y un sumidero común.

TEOREMA DEL FLUJO MINIMO:

Un corte es un conjunto de corte(s) el cual queda como 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.

REDES DE PAREO:

Dado un grafo un pareo es un subconjunto de aristas los cuales no tienen vértices en común.

REDES DE PETRI:

Es un grafo dirigido bipartito, con un estado inicial, llamado marcación inicial. Los dos componentes principales de la red de Petri son los sitios (también conocidos como estados) y las transiciones.

Gráficamente los sitios son dibujados como circulo y las transiciones como barras o rectángulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso especifico, el cual es indicado por un número entero positivo, y vas de sitio a transición y viceversa.

Referencias:

6.5 Redes (teorema de flujo máximo, teorema de flujo mínimo, pareos y redes de Petri) - Jose L. Sanchez Valdez (google.com)

untitled (us.es)