6.5 Un primo flusso ammissibile¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Slide · Esercizi: Flusso di costo minimo · App: Flusso di costo minimo: cancellazione dei cicli e cammini minimi successivi
- Un algoritmo che migliora un flusso ammissibile ha bisogno di un flusso ammissibile da cui partire. Con la sostituzione del Capitolo 4 possiamo supporre \(\vet{l}=\vet{0}\).
Definizione 6.11: rete ausiliaria
Sia \(G=(N,A)\) una rete bilanciata con \(\vet{l}=\vet{0}\), e sia \(D=\sum_{i \in N: b_i>0} b_i\) la sua offerta totale. La rete ausiliaria aggiunge a \(G\) una super sorgente \(s\) e un super pozzo \(t\), un arco \((s,i)\) con capacità \(b_i\) per ogni nodo di offerta \(i\), e un arco \((i,t)\) con capacità \(-b_i\) per ogni nodo di domanda \(i\); gli archi di \(A\) mantengono le loro capacità.
Proposizione 6.12: un flusso ammissibile da un flusso massimo
La rete \(G\) ha un flusso ammissibile se e solo se il flusso massimo da \(s\) a \(t\) della rete ausiliaria ha valore \(D\). In tal caso, la restrizione di un flusso massimo agli archi di \(A\) è un flusso ammissibile di \(G\).
Dimostrazione
Il valore di un flusso da \(s\) a \(t\) è il flusso uscente da \(s\), al più la capacità totale \(D\) degli archi \((s,i)\).
-
Solo se. Sia \(\vet{x}\) ammissibile, e poniamo \(x_{si}=b_i\) sugli archi \((s,i)\) e \(x_{it}=-b_i\) sugli archi \((i,t)\). In un nodo di offerta il flusso uscente meno entrante diventa \(b_i-x_{si}=0\), in un nodo di domanda \(b_i+x_{it}=0\), e i nodi di trasbordo non cambiano: è un flusso da \(s\) a \(t\) di valore \(D\), quindi massimo.
-
Se. Sia \(D\) il valore di un flusso massimo. Allora tutti gli archi \((s,i)\) sono saturi. Il valore è anche il flusso entrante in \(t\), e gli archi \((i,t)\) hanno capacità totale \(\sum_{i: b_i<0}(-b_i)=D\), perché la rete è bilanciata: anch'essi sono saturi.
-
La conservazione del flusso in \(i \in N\) dà allora, lungo gli archi di \(A\), flusso uscente meno entrante pari a \(x_{si}-x_{it}=b_i\), e le capacità sono rispettate: la restrizione ad \(A\) è un flusso ammissibile. □
-
Calcoliamo il flusso massimo con l'algoritmo di Edmonds–Karp del Capitolo 5: una visita in ampiezza da \(s\) nella rete residua, che esamina gli archi uscenti da un nodo per indice crescente della testa (\(s\) prima del nodo \(1\), \(t\) dopo il nodo \(n\)).
-
Il flusso massimo ignora i costi: dà un flusso ammissibile, di solito lontano dall'ottimo.
Esempio 6.5: un flusso ammissibile della rete di riferimento
La rete di riferimento ha \(D=5+2=7\). La rete ausiliaria aggiunge gli archi \((s,1)\), \((s,2)\) con capacità \(5\), \(2\), e \((4,t)\), \((6,t)\) con capacità \(3\), \(4\) (in rosso e tratteggiati nella figura). I cammini aumentanti dell'algoritmo di Edmonds–Karp sono:
| cammino | nodi | unità |
|---|---|---|
| \(1\) | \(s,2,4,t\) | \(2\) |
| \(2\) | \(s,1,2,4,t\) | \(1\) |
| \(3\) | \(s,1,2,4,6,t\) | \(1\) |
| \(4\) | \(s,1,3,5,6,t\) | \(2\) |
| \(5\) | \(s,1,3,5,4,6,t\) | \(1\) |
Il valore è \(7=D\), quindi la rete ha un flusso ammissibile. Ogni arco porta \(x_{ij}/u_{ij}\):
La restrizione ad \(A\) è \((2,3,4,0,3,0,2,1,2)\): su questa istanza è il flusso ottimo \(\tilde{\vet{x}}\) del Capitolo 4. È una coincidenza, perché la visita non guarda mai i costi.
Una super sorgente che alimenta i nodi di offerta e un super pozzo alimentato dai nodi di domanda trasformano l'ammissibilità in un problema di flusso massimo: la rete ha un flusso ammissibile se e solo se il flusso massimo satura tutti gli archi nuovi.