Algoritmos y Estructura de Datos

Flujos Máximos y Mínimos

Flujo Maximo

Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo consideraremos un flujo inicial en cada arista iguala cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.

* Las capacidades deben representar la máxima cantidad de flujo que pueden pasar por los diferentes arcos de la red.

* Si no existe límite de capacidad entre un nodo “A” y un nodo “B” entonces, se debe asignar una capacidad X muy grande.

Flujo Minimo

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 Pareo

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

Redes de Preti

Es un grafo dirigido bipartito, con un estado inicial, llamado marcación inicial. Los dos componentes principales de la red de Petrí son los sitios (también conocidos como estados) y las transiciones. Gráficamente, los sitios son dibujados como círculos y las transiciones como barras o rectángulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso específico, el cual es indicado por un número entero positivo, y van de sitio a transición y viceversa.

Link de apoyo

Flujo maximo en redes

ALGORITMO DE FORD-FULKERSON

Flujo maximo y corte minimo sobre CUDA