Scribd
Cargar
304 vistas6 páginas

Flujo Maximo

El documento explica el concepto de flujo máximo en grafos dirigidos y no dirigidos, donde un nodo es el origen y otro el destino. Describe el método de Ford-Fulkerson para encontrar el flujo máximo, buscando caminos con flujo positivo entre el origen y destino. El algoritmo actualiza las capacidades de los arcos con el flujo mínimo encontrado, repitiendo hasta no encontrar más caminos posibles.

Cargado por

Howard Figueroa
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
304 vistas6 páginas

Flujo Maximo

El documento explica el concepto de flujo máximo en grafos dirigidos y no dirigidos, donde un nodo es el origen y otro el destino. Describe el método de Ford-Fulkerson para encontrar el flujo máximo, buscando caminos con flujo positivo entre el origen y destino. El algoritmo actualiza las capacidades de los arcos con el flujo mínimo encontrado, repitiendo hasta no encontrar más caminos posibles.

Cargado por

Howard Figueroa
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

FLUJO MAXIMO

GRAFICO DE NODOS

GRAFOS : es un conjunto de varios nodos ( puntos en el espacio ) y arcos ( lineas ) que salen de un determinado
nodo hacia otro. Los grafos pueden ser dirigidos, cuando cada arco tiene un nodo origen y uno destino ( es decir los
arcos tienen un sentido ), o no dirigidos en caso contrario.
1. Grafo dirigido 2. Grafo no dirigido

20 2 20 2

1 25 1 25
10 10

4 4
3 3
10 10
FLUJO MAXIMO

(Ahora bien despues de haber definido que es un grafo ) Existe


un grafo dirigido o no dirigido ( comunmente dirigido en la
mayoria de las aplicaciones reales), donde uno de los vertices es
considerado como “origen” y otro como el “destino”, de tal
manera que algun material u objeto puede fluir desde el origen
hasta el destino; a la cantidad de material u objeto que circula
por el grafo se le denomina flujo.
METODO FORD FULKERSON

Para la resolución de problemas de flujo máximo se requiere el uso del método Ford
Fulkerson. Este método propone buscar caminos en los que se pueda aumentar el
flujo hasta que se alcance el flujo máximo, la idea es encontrar una ruta de
penetración con un flujo positivo neto que una los nodos de origen y destino.

• El flujo es siempre positivo y con unidades enteras.


• El flujo a través de un arco es menor o igual que la capacidad.
• El flujo que entra en un nodo es igual al que sale de él.
ALGORITMO PARA RESOLVER

Inicio

Direccionar flujos e iniciar en ceros

Obtener trayectorias buscando siempre


el mayor flujo

Escoger el menor flujo de la trayectoria

Actualizar el grafico con las capacidades


minimas

Buscar nueva trayectoria en aumento y


repetir hasta que no existan más

Fin
FORMULARIO

Cij,ji = (Ci-K, Cj+K), donde:

C : capacidad
Ij : índices de los nodos
K : es el minimo flujo que pasa por el nodo, se calcula como k= min(capacidades de la ruta).

También podría gustarte