Il Problema del Flusso Massimo

Questa tipologia di problema può essere vista come una restrizione dei problemi di MCF in cui assumiamo che:

• I costi sono nulli;
• Gli sbilanciamenti sono nulli;
• Si aggiunge un arco fittizio da $t$ a $s$ con costo -1 e capacità infinita.
• Graficamente

Tagli

Definiamo un taglio in una rete $G=(N,A)$ come una coppia $(N',N'')$ di sottoinsiemi di $N$ tali per cui $N'\cap N''=\empty$ e $N'\cup N''=N$.

Un $(s,t)$-taglio in una rete G è un taglio $(N_s,N_t)$ in cui $s\in N_s$ e $t\in N_t$.

Dato un $(s,t)$-taglio, definiamo i seguenti sottoinsiemi di A:

• $A^+(N_s,N_t)=\{(i,j\in A|i\in N_s \land j\in N_t)\}$, ovvero l'insieme degli archi che partono da nodi in $N_s$ e arrivano in nodi in $N_t$;
• $A^-(N_s,N_t)=\{(i,j\in A|i\in N_t \land j\in N_s)\}$, ovvero l'insieme degli archi che partono da nodi in $N_t$ e arrivano in nodi in $N_s$.
• Esempio di taglio

Lemma

Per ogni $(s,t)$-taglio $(N_s,N_t)$ e ogni flusso ammissibile $x$ con valore $v$:

1. Il flusso del taglio $v$ è:

   $$ v=\sum_{(i,j)\in A^+(N_s,N_t)}x_{ij}-\sum_{(i,j)\in A^-(N_s,N_t)}x_{ij} $$

2. La capacità del taglio $v$ è:

   $$ v\leq\sum_{(i,j)\in A^+(N_s,N_t)}u_{ij} $$

Dimostrazione su slide.

Questo lemma ci dice che:

$$ v=x(N_s,N_t)\leq u(N_s,N_t) $$

Il valore di un flusso ammissibile è sempre minore o uguale della capacità di qualunque taglio.

Grafi residui

Data una rete $G=(N_G,A_G)$ e un flusso ammissibile $x$, il grafo residuo $G_x$ è il multigrafo $(N_{G_x},A_{G_x})$ tale che: