Exposicion Ford fulkerson algoritmo y puntos clave.pptx

Ford

1. Algoritmo de Ford-Fulkerson{ } < Por =“Jorge Montenegro"/> <!—Estructura De Datos ->

2. Contenido Introducción Puntos Clave Componentes Funcionamiento Aplicacion Real Pros y Contras Codigo 01 02 03 04 05 06 07

3. Algoritmo de Ford– Fulkerson { ¿ Que Es ? ¿Qué es el flujo máximo ? Es un algoritmo que permite encontrar el flujo máximo en una red de flujo (un grafo con capacidades).Se basa en encontrar caminos desde el origen hasta el sumidero que todavía tengan capacidad disponible. El flujo máximo es la cantidad máxima de recursos que se puede transportar desde un punto de origen (fuente) hasta un punto de destino (sumidero) a través de una red, sin exceder las capacidades de las conexiones (aristas). Queremos saber cuántos paquetes como máximo pueden enviarse por día desde la bodega central hasta todas las ciudades, sin superar la capacidad de transporte de cada ruta . Nodos: Bodegas, centros de distribución, y ciudades destino. Aristas: Carreteras o rutas entre ellos. Capacidades: Máxima cantidad de paquetes que pueden pasar por cada ruta al día } Ejemplo: Envío de paquetes por una red logística

4. Puntos clave { } Flujo inicial – Se parte desde cero Repetición del proceso – Se continúa iterando Búsqueda de caminos – Se identifican rutas posibles Flujo máximo alcanzado – Resultado final Capacidad mínima – Se detecta la restricción Aumento de flujo – Se incrementa el flujo total 01 05 02 06 03 04

5. Componentes del Algoritmo de Ford- Fulkerson { } Red de Flujo (Grafo dirigido con capacidades) Nodos (vértices): representan los puntos de entrada, salida y conexión. Aristas dirigidas: representan los caminos con una capacidad máxima asignada. Nodo fuente ( source ) Es el origen del flujo, donde todo comienza. Nodo sumidero ( sink ) Es el destino del flujo, donde todo debe llegar. Caminos aumentantes Caminos desde la fuente al sumidero que todavía tienen capacidad disponible para aumentar el flujo. 5. Flujo residual y red residual La capacidad restante que queda en las aristas después de enviar flujo. La red residual se actualiza cada vez que se encuentra un nuevo camino. 6 . Regla de actualización del flujo Cada vez que se encuentra un camino aumentante, se suma flujo a las aristas hacia adelante y se resta flujo en sentido contrario. 7 . Condición de parada El algoritmo termina cuando ya no se pueden encontrar caminos aumentantes desde la fuente hasta el sumidero.

6. Funcionamiento { } Origen: nodo 1 Destino : nodo 5 Se elige el camino con mayor capacidad Se calcula el flujo máximo posible en ese camino:  k = min(∞, 30, 20) = 20 1 → 3 (30) → 5 (20) Se actualizan las capacidades:  C13 = 10, C31 = 20  C35 = 0, C53 = 20

7. Red de distribucion de agua Cada arista de la red tiene una capacidad específica que limita el flujo de agua entre nodos. El sistema se modela como una red : Nodos = tanques y puntos de consumo (casas, fábricas, etc .) Aristas = tuberías que conectan esos nodos Permite optimizar la distribución del recurso de forma rápida y confiable El algoritmo de Ford- Fulkerson calcula el flujo máximo que puede ser enviado desde el tanque a los puntos de consumo. Eficiencia del algoritmo Capacidades de las tuberías Flujo Maximo } Aplicabilidad en la vida real {

8. Ventajas Del Algoritmo . Limitaciones del algoritmo . Poca eficiencia en redes grandes. El número de iteraciones puede crecer considerablemente, especialmente si los aumentos de flujo son pequeños. Depende del método de búsqueda. Su rendimiento varía según se use BFS, DFS u otro enfoque para encontrar los caminos aumentantes. Puede ser lento con ciclos o capacidades pequeñas. En ciertos casos, especialmente con ciclos y flujos fraccionarios, puede tardar mucho en converger. Sencillo y fácil de implementar. Su lógica es intuitiva y se basa en pasos repetitivos claros. Eficiente en redes pequeñas o medianas. Ofrece buenos resultados sin requerir gran potencia computacional. Flexible. Se puede adaptar a distintos tipos de grafos (dirigidos/no dirigidos, con capacidades enteras o reales). Pros y Contras del Algoritmo Ford- Fulkerson { }

9. Código { } def ford_fulkerson ( grafo , nodo_fuente , nodo_sumidero ):     grafo_residual = [ fila [:] for fila in grafo ]   # Copia del grafo     padres = [ - 1 ] * len ( grafo )     flujo_maximo =     # Mientras exista un camino aumentante desde la fuente al sumidero     while existe_camino_aumentante ( grafo_residual , nodo_fuente , nodo_sumidero , padres ):         # Encontrar el flujo mínimo en ese camino         flujo_camino = flujo_minimo_en_camino ( grafo_residual , nodo_fuente , nodo_sumidero , padres )         # Actualizar capacidades residuales         actualizar_grafo_residual ( grafo_residual , padres , nodo_fuente , nodo_sumidero , flujo_camino )         # Sumar flujo al total         flujo_maximo += flujo_camino     return flujo_maximo

10. Gracias { } < Por =“Jorge Montenegro"/> <!—Estructura De Datos -->