Introducción

Los algoritmos de flujo máximo son una clase de algoritmos utilizados para encontrar el flujo máximo posible en una red de flujo. Estos algoritmos tienen aplicaciones en diversas áreas como la optimización de redes, la planificación de recursos, y la ingeniería de tráfico.

Conceptos Básicos

Antes de profundizar en los algoritmos, es esencial entender algunos conceptos clave:

Red de Flujo: Una red dirigida donde cada arista tiene una capacidad y cada flujo debe respetar estas capacidades.
Fuente (s): Nodo de inicio donde el flujo entra en la red.
Sumidero (t): Nodo de destino donde el flujo sale de la red.
Capacidad (c): La cantidad máxima de flujo que una arista puede soportar.
Flujo (f): La cantidad de flujo que realmente pasa por una arista.

Notación

\( G(V, E) \): Grafo dirigido con conjunto de vértices \( V \) y conjunto de aristas \( E \).
\( c(u, v) \): Capacidad de la arista de \( u \) a \( v \).
\( f(u, v) \): Flujo actual en la arista de \( u \) a \( v \).

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson es uno de los métodos más conocidos para resolver el problema del flujo máximo. Utiliza el concepto de caminos aumentantes y se basa en la búsqueda de estos caminos para incrementar el flujo total.

Pasos del Algoritmo

Inicialización: Inicializar el flujo en todas las aristas a 0.
Búsqueda de Camino Aumentante: Mientras exista un camino aumentante desde la fuente \( s \) hasta el sumidero \( t \) en la red residual, aumentar el flujo a lo largo de este camino.
Actualización del Flujo: Actualizar el flujo y las capacidades residuales.
Repetición: Repetir el proceso hasta que no haya más caminos aumentantes.

Ejemplo de Implementación

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.ROW = vertices

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def bfs(self, s, t, parent):
        visited = [False] * self.ROW
        queue = []
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)

            for v, w in self.graph[u]:
                if visited[v] == False and w > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u

        return True if visited[t] else False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.ROW
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink

            while s != source:
                for v, w in self.graph[parent[s]]:
                    if v == s:
                        path_flow = min(path_flow, w)
                s = parent[s]

            v = sink
            while v != source:
                u = parent[v]
                for i, (vertex, weight) in enumerate(self.graph[u]):
                    if vertex == v:
                        self.graph[u][i] = (vertex, weight - path_flow)
                for i, (vertex, weight) in enumerate(self.graph[v]):
                    if vertex == u:
                        self.graph[v][i] = (vertex, weight + path_flow)
                v = parent[v]

            max_flow += path_flow

        return max_flow

# Ejemplo de uso
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5

print("El flujo máximo es:", g.ford_fulkerson(source, sink))

Explicación del Código

Inicialización del Grafo: Se crea una clase Graph que inicializa el grafo y permite agregar aristas con capacidades.
Búsqueda en Anchura (BFS): Se utiliza para encontrar caminos aumentantes desde la fuente hasta el sumidero.
Ford-Fulkerson: Implementa el algoritmo principal que busca caminos aumentantes y actualiza el flujo y las capacidades residuales.

Ejercicios Prácticos

Ejercicio 1: Implementación Básica

Problema: Implementa el algoritmo de Ford-Fulkerson para un grafo con 4 nodos y las siguientes aristas y capacidades:

(0, 1, 10)
(0, 2, 5)
(1, 2, 15)
(1, 3, 10)
(2, 3, 10)

Solución:

g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 15)
g.add_edge(1, 3, 10)
g.add_edge(2, 3, 10)

source = 0
sink = 3

print("El flujo máximo es:", g.ford_fulkerson(source, sink))

Ejercicio 2: Análisis de Complejidad

Problema: Analiza la complejidad temporal del algoritmo de Ford-Fulkerson en términos del número de vértices \( V \) y el número de aristas \( E \).

Solución:

La complejidad temporal del algoritmo de Ford-Fulkerson depende de la implementación de la búsqueda de caminos aumentantes. Si se utiliza BFS, la complejidad es \( O(E \cdot f) \), donde \( f \) es el flujo máximo.

Conclusión

En esta sección, hemos explorado los conceptos básicos y la implementación del algoritmo de Ford-Fulkerson para resolver problemas de flujo máximo en redes. Este algoritmo es fundamental en la teoría de grafos y tiene numerosas aplicaciones prácticas. En la siguiente sección, profundizaremos en otros algoritmos de flujo máximo, como el algoritmo de Edmonds-Karp y el algoritmo de Push-Relabel.

Algoritmos de Flujo Máximo

Introducción

Conceptos Básicos

Notación

Algoritmo de Ford-Fulkerson

Pasos del Algoritmo

Ejemplo de Implementación

Explicación del Código

Ejercicios Prácticos

Ejercicio 1: Implementación Básica

Ejercicio 2: Análisis de Complejidad

Conclusión

Algoritmos Avanzados

Módulo 1: Introducción a los Algoritmos Avanzados

Módulo 2: Algoritmos de Optimización

Módulo 3: Algoritmos en Grafos

Módulo 4: Algoritmos de Búsqueda y Ordenación

Módulo 5: Algoritmos de Aprendizaje Automático

Módulo 6: Casos de Estudio y Aplicaciones

Módulo 7: Proyecto Final