Algoritmos Fundamentales en Grafos: Caminos Mínimos, Árboles de Expansión y Flujo Máximo

Algoritmo de Dijkstra: Caminos Mínimos en Grafos

El algoritmo de Dijkstra es fundamental para encontrar los caminos más cortos desde un nodo fuente único hacia todos los demás nodos en un grafo con pesos de arista no negativos.

Definición de Elementos Clave:

• P: Conjunto de nodos permanentes (ya visitados y con su camino mínimo finalizado).
• T: Conjunto de nodos temporales (pendientes de visitar o actualizar).
• u_i: Longitud del camino mínimo actual desde el vértice inicial hasta el vértice i, para todo i = 1, ..., n (donde n es el número de vértices del grafo).
• pred: Vector que almacena los predecesores de cada nodo en el camino mínimo.

Pasos del Algoritmo de Dijkstra:

1. Paso 0: Inicialización

   Se etiquetan los nodos con la longitud del arco que los une con el origen, asignando u₁ = 0 para el nodo fuente y u_j = d_1j para todo j = 2, ..., n. Se inicializan los conjuntos: P = {1} (el nodo fuente es permanente), T = {2, ..., n} (los demás son temporales), y pred(j) = 1 para todo j = 2, ..., n.

2. Paso 1: Selección del Nodo Permanente

   En cada iteración, se elige la etiqueta que se hará permanente. Es decir, se busca un nodo k ∈ T tal que u_k = min_j∈T {u_j}. Se actualizan los conjuntos: P = P ∪ {k} y T = T − {k}. Si T = ∅, el algoritmo se detiene, ya que todos los nodos han sido procesados.

3. Paso 2: Actualización de Etiquetas Temporales

   Se revisan las etiquetas temporales. Para todo j ∈ T, se calcula u_j = min{u_j, u_k + d_kj}. Si el mínimo se alcanza con u_k + d_kj, se actualiza pred(j) = k. Posteriormente, se regresa al Paso 1 para la siguiente iteración.

Algoritmo de Prim: Construcción de Árboles de Expansión Mínima

El algoritmo de Prim es utilizado para encontrar un árbol de expansión mínima en un grafo conexo, ponderado y no dirigido. Construye el árbol añadiendo aristas que conectan un nuevo vértice al árbol ya construido, siempre eligiendo la arista de menor peso.

Definición de Elementos Clave:

• G = (V, E): El grafo sobre el que se busca el árbol de expansión de mínimo peso.
• n: El número de nodos del grafo (n = Card(V)).
• T: El árbol de expansión mínima que se está construyendo.
• C_k: El conjunto de nodos ya conectados al árbol hasta la iteración k.
• C̄_k: El conjunto de nodos que aún no están conectados al árbol hasta la iteración k.

Pasos del Algoritmo de Prim:

1. Paso 1: Selección de un Vértice Inicial

   Se inicializan los conjuntos: C₀ = ∅ y C̄₀ = V. Se elige un vértice inicial cualquiera i ∈ V y se establece C₁ = {i} y C̄₁ = V − {i}. Se inicializa el contador de iteraciones k = 2 y el árbol T = ∅.

2. Paso 2: Adición del Vértice Más Cercano al Árbol

   Se selecciona j⁎ ∈ C̄_k-1, un nodo no conectado que se une a algún vértice ya conectado (de C_k-1) mediante la arista de menor peso e_k-1. Se actualizan los conjuntos y el árbol: C_k = C_k-1 ∪ {j⁎}, C̄_k = C̄_k-1 − {j⁎} y T = T ∪ {e_k-1}. Si k = n, el algoritmo termina; en caso contrario, se incrementa k a k + 1 y se repite el Paso 2.

Algoritmo de Kruskal: Construcción de Árboles de Expansión Mínima por Aristas

El algoritmo de Kruskal es otro método para encontrar un árbol de expansión mínima en un grafo conexo y ponderado. A diferencia de Prim, Kruskal se enfoca en seleccionar aristas de menor peso que no formen ciclos.

Definición de Elementos Clave:

• G = (V, E): El grafo sobre el que se busca el árbol de expansión de mínimo peso.
• n: El número de nodos del grafo (n = Card(V)).
• T: El árbol de expansión mínima que se está construyendo.

Pasos del Algoritmo de Kruskal:

1. Paso 1: Elección de la Arista Inicial

   Se inicializa el contador k = 1. Se elige la arista de mínimo peso e₁ del grafo y se establece T = {e₁}. Se actualiza el conjunto de aristas disponibles: E = E − {e₁}.

2. Paso 2: Construcción del Árbol

   Se incrementa k a k + 1. Se selecciona e_k ∈ E, la arista de mínimo peso restante tal que T ∪ {e_k} forma un grafo acíclico. Entonces, se actualiza T = T ∪ {e_k}.

3. Paso 3: Criterio de Parada

   Si el árbol T tiene n − 1 aristas (lo que indica que todos los nodos están conectados y se ha formado un árbol), el algoritmo termina. En caso contrario, se regresa al Paso 2.

Problema de Flujo Máximo en Redes de Transporte

El problema de flujo máximo busca determinar la máxima cantidad de "flujo" que puede pasar desde una fuente a un sumidero en una red de transporte, respetando las capacidades de cada arco.

Definición de una Red de Transporte:

Una red de transporte se define como un grafo dirigido con las siguientes características:

• Existe una única fuente (s), es decir, un nodo en el que no incide ningún arco.
• Existe un único sumidero (t), es decir, un nodo del que no sale ningún arco.
• El grafo G está valorado, lo que significa que cada arco tiene asociado un valor no negativo denominado capacidad del arco.
• Además, cada vértice es alcanzable desde la fuente y el sumidero es alcanzable desde todos los vértices.

Algoritmo de Ford-Fulkerson: Resolución del Flujo Máximo

El algoritmo de Ford-Fulkerson es un método iterativo para encontrar el flujo máximo en una red de transporte. Se basa en la búsqueda de caminos de aumento en la red residual.

Pasos del Algoritmo de Ford-Fulkerson:

1. Paso 1: Inicialización

   Se inicia con un flujo cero (φ_ij = 0) en todos los arcos y capacidades residuales (c*_ij = c_ij). La fuente se etiqueta como s → (-, ∞).

2. Paso 2: Búsqueda de Camino de Aumento

   Se busca un camino de aumento desde nodos ya etiquetados a otros no etiquetados. Si existe un arco (i, j) con capacidad residual positiva, se etiqueta j → (i+, δ_j). Si existe un arco (j, i) con flujo positivo, se etiqueta j → (i−, δ_j). Este proceso se repite hasta etiquetar el sumidero o hasta que no sea posible avanzar más.

3. Paso 3: Aumento del Flujo

   Si se encontró un camino de aumento, se incrementa el flujo en ese camino en una cantidad igual a δ_t. Se ajustan las capacidades residuales (restando en arcos en la dirección del flujo y sumando en arcos en la dirección opuesta). Se borran todas las etiquetas (salvo la de la fuente) y se regresa al Paso 2.

4. Paso 4: Criterio de Parada y Resultado

   Si ya no es posible encontrar caminos de aumento, el algoritmo se detiene. El flujo obtenido es el flujo máximo de la red. El corte mínimo se determina por los nodos etiquetados frente a los no etiquetados en la última iteración.