Fins ara les arestes de Rutalia mesuraven el cost de travessar-les (minuts) o de construir-les (euros de fibra). Aquesta lliçó els dona un tercer significat: capacitat — quants paquets per hora poden circular per cada carrer. La pregunta canvia de naturalesa: ja no busquem el millor camí per a una furgoneta, sinó el cabal màxim que tota la flota pot sostenir entre el magatzem i un barri en hora punta. Aquest és el problema del flux màxim, un dels grans clàssics dels grafs, amb una teoria preciosa (la xarxa residual, el teorema max-flow min-cut) i un abast sorprenent: al final veurem que fins i tot assignar repartidors a comandes és, en secret, un problema de flux.

1. El problema de flux: capacitats, conservació, font i embornal
2. El parany voraç i la xarxa residual: per què calen arestes de retrocés
3. Ford-Fulkerson: el mètode dels camins augmentants
4. Edmonds-Karp: Ford-Fulkerson amb el BFS de 03-02
5. La xarxa d'hora punta de Rutalia, resolta pas a pas
6. El teorema max-flow min-cut: el coll d'ampolla físic
7. L'assignació com a flux: avançament de 03-06

Una xarxa de flux és un graf dirigit on cada aresta (u, v) té una capacitat c(u, v) ≥ 0, amb dos nodes distingits: la font s (on el flux neix) i l'embornal t (on mor). Un flux assigna a cada aresta una quantitat f(u, v) complint:

• Restricció de capacitat: 0 ≤ f(u, v) ≤ c(u, v). Per un carrer de 8 paquets/hora no en passen 9.
• Conservació: a tot node llevat de s i t, el que entra és igual al que surt. Les cruïlles no fabriquen ni emmagatzemen paquets.

El valor del flux és el que surt net de s (equivalentment, el que arriba a t). El problema del flux màxim: trobar el flux de valor màxim.

Escenari Rutalia: és hora punta i el Centre Històric (CEN) concentra les comandes. Del Magatzem (ALM) surten paquets cap a CEN a través de la zona del Mercat (MER), el Pont del Riu (RIO) i la Ciutat Universitària (UNI). Les capacitats (paquets/hora, estimades per trànsit i nombre de furgonetes que admet cada eix, en el sentit útil de l'hora punta) són:

Pregunta: quants paquets/hora pot injectar Rutalia al Centre? A ull no és obvi: d'ALM en surten 12 + 11 = 23, a CEN n'entren 6 + 9 + 8 = 23… però veurem que la resposta real és 22, i que el límit no és ni a la sortida ni a l'arribada, sinó en un tall intermedi.

Primer impuls: buscar un camí de s a t amb capacitat lliure, enviar-hi tot el possible, repetir. El problema és que una elecció primerenca pot bloquejar combinacions millors. Exemple mínim (subxarxa amb capacitats petites per veure-ho clar):

• ALM→MER: 8, ALM→RIO: 8, MER→CEN: 8, RIO→CEN: 8 i una drecera transversal MER→RIO: 6.
• L'òptim és obvi: 8 per dalt (ALM→MER→CEN) i 8 per baix (ALM→RIO→CEN) = 16, ignorant la drecera.
• Però suposa que el primer camí explorat és ALM→MER→RIO→CEN i hi enviem 6. Ara ALM→MER té 2 de lliures i RIO→CEN en té 2 de lliures: els camins directes només aporten 2 + 2 = 4 més. Total 10. Encallats lluny de 16.

La solució és comptable, no física: permetre desfer decisions. Es defineix la xarxa residual: per a cada aresta amb capacitat c i flux f, la residual conté:

• l'aresta cap endavant amb capacitat c − f (el que encara hi cap), i
• una aresta de retrocés v→u amb capacitat f (el que es pot cancel·lar).

A l'exemple encallat, la xarxa residual conté RIO→MER amb capacitat 6 (retrocés de la drecera). El camí residual ALM→RIO→MER→CEN amb coll 6 "hi envia 6" que en realitat significa: 6 unitats noves entren per baix fins a RIO, i 6 de les que giraven per la drecera cap a RIO es queden a dalt i segueixen cap a CEN. Ningú no circula marxa enrere: només es reescriu la comptabilitat. Total: 16. L'avarícia inicial, corregida sense començar de zero.

Un camí de s a t a la xarxa residual s'anomena camí augmentant; el seu coll d'ampolla és la capacitat residual mínima de les seves arestes.

El mètode de Ford-Fulkerson és exactament aquest bucle:

Propietats clau:

• Amb capacitats enteres, cada iteració augmenta el flux en ≥ 1, per tant acaba; i el flux màxim resultant és enter (teorema d'integralitat — serà crucial a 03-06: "mig repartidor" no existeix).
• Cost: O(m) per iteració de cerca × nombre d'iteracions. Si els camins es trien malament, les iteracions poden ser fins a f* (el valor del flux màxim): O(m · f*). Existeix un exemple clàssic amb capacitats 1.000.000 i una drecera de capacitat 1 on una elecció perversa alterna 2 milions de caminets d'1 unitat. "Ford-Fulkerson" és un mètode; falta fixar com es busca el camí.

Edmonds-Karp concreta l'elecció: buscar sempre el camí augmentant amb menys arestes, és a dir, amb el BFS de 03-02 sobre la xarxa residual. Aquest detall fita les iteracions en O(n·m) independentment de les capacitats, donant un cost total de O(n · m²).

Lectura guiada del codi:

• La xarxa residual res unifica marge i retrocés: res[u][v] és "quant més puc empènyer d'u a v ara mateix", tant si (u,v) era una aresta real com si és l'ombra d'una aresta contrària.
• El BFS és literalment el de 03-02 amb un filtre extra (c_res > 0) i aturada primerenca en abastar t; pare reconstrueix el camí igual que aleshores.
• Quan no hi ha camí, el conjunt pare (els abastables des de s a la residual) no és un subproducte: és la meitat S del tall mínim, com veurem de seguida. L'algorisme regala el certificat d'optimalitat.

Seqüència de camins augmentants que troba Edmonds-Karp (BFS prioritza els curts):

El flux final per aresta: ALM→MER 12/12, ALM→RIO 10/11, RIO→MER 1/4, MER→CEN 6/6, MER→UNI 7/7, RIO→CEN 9/9, UNI→CEN 7/8. Comprova la conservació a MER: entren 12 + 1 = 13, surten 6 + 7 = 13 ✓. La iteració 4 és la xarxa residual en acció: el paquet extra entra pel riu i usa la drecera RIO→MER per abastar el marge que quedava a UNI→CEN.

Un tall s-t és una partició dels nodes en (S, T) amb s ∈ S i t ∈ T; la seva capacitat és la suma de capacitats de les arestes que van de S a T (només aquest sentit). Tot flux ha de travessar qualsevol tall; per tant, flux màxim ≤ capacitat de qualsevol tall. El resultat profund és la igualtat:

Teorema max-flow min-cut: el valor del flux màxim és exactament la capacitat del tall mínim.

I la demostració és constructiva amb el que ja tenim: quan Edmonds-Karp s'atura, S = {abastables des de s a la residual} defineix un tall les arestes S→T del qual estan totes saturades (si tinguessin marge, el BFS hauria creuat). Aquell tall té capacitat = flux actual, i com que cap flux no supera cap tall, tots dos són òptims alhora. L'algorisme no només dona el número: dona el certificat, igual que la fita del B&B a 02-03 certificava el 35,22 del TSP.

A Rutalia: S = {ALM, RIO, MER}, T = {UNI, CEN}. Les arestes del tall mínim són MER→UNI (7), MER→CEN (6) i RIO→CEN (9): 7 + 6 + 9 = 22. Interpretació física immediata per a l'equip d'operacions:

• El límit de 22 paquets/hora no és a la sortida del magatzem (23) ni als accessos finals al Centre (23), sinó a l'anell intermedi.
• Si l'ajuntament pregunta quins carrers ampliar, la resposta del teorema és quirúrgica: només els del tall mínim. Ampliar ALM→MER o UNI→CEN no afegeix ni un paquet; ampliar RIO→CEN en 1 puja el cabal a 23 (fins que un altre tall passi a ser el mínim — recalcula després de cada canvi).

Fixa't en el paral·lelisme amb 03-02: allà preguntàvem si un tall desconnecta (connectivitat); aquí, quant estrangula (capacitat). El flux màxim és la versió quantitativa de la robustesa.

La sorpresa final: el flux màxim resol problemes on no hi ha res que "flueixi". Es poden assignar 3 repartidors a 3 comandes si cada repartidor només pot atendre certes comandes (per zona, per tipus de vehicle)? Construïm aquesta xarxa:

• Font s → cada repartidor, capacitat 1 (cadascú atén com a molt una comanda).
• Repartidor → cada comanda compatible, capacitat 1.
• Cada comanda → embornal t, capacitat 1 (cada comanda la serveix com a molt un).

Cada unitat de flux entera és una parella repartidor-comanda, i el flux màxim és el nombre màxim d'assignacions compatibles simultànies. La integralitat de Ford-Fulkerson garanteix que la solució no parteix repartidors en fraccions. Aquesta reducció —convertir un problema en un altre de ja resolt— és una de les armes més elegants de l'algorísmica, i és exactament el pont cap a la propera lliçó: l'aparellament en grafs bipartits (03-06), on la desenvoluparem amb tot detall i amb els seus algorismes especialitzats.

• Ometre les arestes de retrocés: l'error número u. Sense elles, el resultat depèn de l'ordre d'exploració i pot quedar-se curt (10 davant de 16 al nostre exemple mínim). Si el teu "flux màxim" canvia en reordenar veïns, gairebé segur que és això.
• Modelar la xarxa com a no dirigida: les capacitats d'hora punta tenen sentit — un carrer de doble sentit es modela com dues arestes dirigides, cadascuna amb la seva capacitat. Copiar el graf de 03-01 sense dirigir-lo produeix respostes sense significat.
• Usar DFS per al camí augmentant amb capacitats grans: Ford-Fulkerson pur pot iterar milions de vegades (l'exemple de la drecera de capacitat 1). El BFS d'Edmonds-Karp fita les iteracions sense dependre de les capacitats. Per a xarxes serioses hi ha algorismes millors (Dinic, push-relabel); networkx.maximum_flow els porta de sèrie.
• Llegir el tall mínim com "les arestes saturades": hi ha arestes saturades que no són al tall mínim (ALM→MER va a 12/12 i no hi és). El tall és S→T amb S = abastables a la residual; la saturació és necessària però no suficient.
• Oblidar verificar la conservació en depurar: suma entrades i sortides de cada node intermedi. És l'assert més barat i delator de tota aquesta lliçó.
• Consell: dibuixa sempre la xarxa residual després de cada augment en exemples petits. El moment "aha" d'aquesta lliçó és veure com un retrocés converteix una mala decisió en reversible.

1. Ampliació quirúrgica. Usant edmonds_karp, comprova quant millora el cabal de la xarxa d'hora punta si (a) ALM→MER passa de 12 a 15, (b) RIO→CEN passa de 9 a 11. Explica tots dos resultats amb el tall mínim abans d'executar el codi, i verifica-ho.
2. El pitjor tall de l'analista. Calcula a mà la capacitat dels talls S = {ALM} i S = {ALM, MER, RIO, UNI} de la xarxa d'hora punta i comprova que tots dos superen 22. Què et diu això sobre usar "el que surt del magatzem" com a estimació de la capacitat de repartiment?
3. Assignació exprés. Rutalia té 3 repartidors amb compatibilitats: R1→{P1, P2}, R2→{P2}, R3→{P2, P3}. Munta la xarxa d'assignació (font, embornal, capacitats 1) i calcula amb edmonds_karp quantes comandes poden servir-se alhora. Hi ha assignació perfecta?

Exercici 1:

(a) ALM→MER no pertany al tall mínim {MER→UNI, MER→CEN, RIO→CEN}: ampliar-la és llençar els diners, l'estrangulament segueix aigües avall. (b) RIO→CEN sí que és al tall: ampliar en 2 puja el tall a 24, però aleshores mana un altre límit (amb 23 se satura la sortida ALM: 12+11) i només es guanya 1. Els talls es rellevan: després de cada obra cal recalcular.

Exercici 2:

• S = {ALM}: arestes ALM→MER (12) + ALM→RIO (11) = 23.
• S = {ALM, MER, RIO, UNI}: arestes cap a T = {CEN}: MER→CEN (6) + RIO→CEN (9) + UNI→CEN (8) = 23.

Tots dos talls valen 23 > 22: són fites superiors vàlides però no ajustades. Moralitat: la capacitat de sortida del magatzem (o d'entrada al barri) és una estimació optimista del cabal real; el veritable límit pot amagar-se en qualsevol tall intermedi, i només el flux màxim el troba amb certificat.

Exercici 3:

Flux màxim 3 = assignació perfecta: R1→P1, R2→P2, R3→P3. Fixa't que la voracitat ingènua podia fallar (si R1 prengués P2, R2 quedava sense comanda) i és la maquinària de camins augmentants la que ho redreça — a 03-06 veurem aquesta mateixa correcció amb el seu nom propi: camí alternant.

Hem afegit la tercera lectura d'una aresta —capacitat— i amb ella el problema del flux màxim: cabal de s a t respectant capacitats i conservació. La peça conceptual clau és la xarxa residual, les arestes de retrocés de la qual converteixen les decisions voraces en reversibles i sostenen el mètode de Ford-Fulkerson; la concreció pràctica és Edmonds-Karp, que busca cada camí augmentant amb el BFS de 03-02 i garanteix O(n·m²). I el premi teòric és max-flow min-cut: el flux màxim de l'hora punta de Rutalia és de 22 paquets/hora no pas pel que surt del magatzem ni pel que cap al Centre, sinó per un tall intermedi de tres carrers — el coll d'ampolla físic que diu exactament què ampliar i què no. De regal, una reducció amb futur immediat: l'assignació repartidor-comanda és un flux amb capacitats 1. A 03-06, última lliçó del mòdul, aquesta idea floreix en els algorismes d'aparellament en grafs bipartits: bipartició, camins alternants, l'algorisme hongarès i l'assignació òptima que a 02-01 resolíem amb programació lineal.