5.7 Applicazioni

Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp

5.7.1 Corrispondenza massima in un grafo bipartito

Definizione 5.16: grafo bipartito e corrispondenza

Un grafo non orientato \(H=(V_1 \cup V_2,E)\) è bipartito se \(V_1\) e \(V_2\) sono disgiunti e ogni lato ne ha uno estremo in \(V_1\) e uno in \(V_2\); scriviamo i lati come \(\{i,j\}\) con \(i \in V_1\) e \(j \in V_2\).

• A matching è un insieme \(M \subseteq E\) di lati, nessuno dei quali ha un punto finale comune.

• Il problema di corrispondenza massima richiede una corrispondenza con il maggior numero di lati.

La rete di \(H\) ha i nodi \(\{s\} \cup V_1 \cup V_2 \cup \{t\}\), gli archi \((s,i)\) per \(i \in V_1\), \((i,j)\) per ogni lato \(\{i,j\} \in E\), \((j,t)\) per \(j \in V_2\) e tutte le capacità uguali a \(1\).

• Con \(V_1\) un insieme di lavoratori, \(V_2\) un insieme di lavori e un margine in cui un lavoratore può svolgere un lavoro, viene assegnata una corrispondenza posti di lavoro ai lavoratori, al massimo un posto di lavoro per lavoratore e un lavoratore per posto di lavoro.

• Nell'ordine dei nodi, \(s\) viene per primo e \(t\) per ultimo; gli altri nodi mantengono i loro indici.

Proposizione 5.17: corrispondenze e flussi

Il numero massimo di fronti di una corrispondenza di \(H\) equivale al valore massimo \(\tilde{v}\) di un flusso nella rete di \(H\). Se \(\tilde{\vet{x}}\) è un flusso massimo intero, allora \(M=\{\{i,j\} \in E : \tilde{x}_{ij}=1\}\) è una corrispondenza massima.

Dimostrazione

1. Dagli abbinamenti ai flussi. Dato un corrispondente \(M\), impostare \(x=1\) sugli archi \((s,i)\), \((i,j)\), \((j,t)\) di ogni lato \(\{i,j\} \in M\) e \(x=0\) altrove. Ogni nodo di \(V_1 \cup V_2\) è un punto finale di almeno un lato di \(M\), quindi il flusso è fattibile e il suo valore è \(|M|\).

2. Da flussi interi agli abbinamenti. Sia \(\vet{x}\) un flusso ammissibile intero, quindi \(x_{ij} \in \{0,1\}\). A il nodo \(i \in V_1\) ha il singolo arco entrante \((s,i)\), quindi al massimo un arco \((i,j)\) trasporta flusso; ha un nodo \(j \in V_2\) l'unico arco uscente \((j,t)\), quindi al massimo un arco \((i,j)\) trasporta il flusso. Quindi \(M=\{\{i,j\} : x_{ij}=1\}\) è un corrispondenza. Per \(S=\{s\} \cup V_1\), gli archi in avanti sono gli archi \((i,j)\) e non ci sono archi all'indietro: da Lemma 5.3, \(v=|M|\).

3. Per Corollario 5.10 esiste un flusso massimo intero \(\tilde{\vet{x}}\). Entro l'1, nessuna corrispondenza ha più di lati \(\tilde{v}\) e per 2 la corrispondenza di \(\tilde{\vet{x}}\) ha lati \(\tilde{v}\). □

Esempio 5.9: lavoratori e posti di lavoro

Quattro lavoratori \(V_1=\{1,2,3,4\}\) e tre lavori \(V_2=\{5,6,7\}\) hanno i vantaggi

\[ E=\big\{\{1,5\},\{1,6\},\{2,5\},\{3,6\},\{3,7\},\{4,6\}\big\}. \]

L'algoritmo Edmonds–Karp sulla rete di \(H\), con i nodi nell'ordine \(s,1,2,\dots,7,t\), dà:

iterazione e percorso aumentante	\(r_{ij}\) su \(P\)	archi all'indietro	\(\delta\)	\(v\)
\(1\)	\(s,1,5,t\)	\(1,1,1\)	–	\(1\)	\(1\)
\(2\)	\(s,3,6,t\)	\(1,1,1\)	–	\(1\)	\(2\)
\(3\)	\(s,4,6,3,7,t\)	\(1,1,1,1,1\)	\((6,3)\)	\(1\)	\(3\)

• L'iterazione \(3\) utilizza l'arco all'indietro \((6,3)\): il lavoratore \(3\) lascia il lavoro \(6\) per il lavoro \(7\) e il lavoratore \(4\) accetta il lavoro \(6\).

• L'abbinamento massimo è \(M=\{\{1,5\},\{3,7\},\{4,6\}\}\), con lati \(3\); il lavoratore \(2\) resta senza lavoro. Dentro nella figura gli archi con flusso \(1\) sono blu.

• Alla fermata cerca le etichette \(S=\{s,1,2,4,5,6\}\); gli archi anteriori del taglio sono \((s,3)\), \((5,t)\), \((6,t)\), con capacità \(3=|M|\).

5.7.2 Percorsi arcodisgiunti

• Due percorsi diretti sono arco-disgiunti se non hanno arco in comune; possono condividere nodi.

Teorema 5.18: Menger, versione ad arco

Sia \(G=(N,A)\) un grafo diretto e \(s \neq t\) due nodi. Il numero massimo di percorsi diretti a coppie di archi disgiunti da \(s\) a \(t\) è uguale al numero minimo di archi la cui rimozione non lascia alcun percorso diretto da \(s\) a \(t\).

Dimostrazione

Assegna ad ogni arco la capacità \(1\) e lascia che \(\tilde{v}\) sia il valore massimo di un flusso.

1. I percorsi danno flussi. La somma dei vettori di incidenza dei percorsi arcodisgiunti \(k\) da \(s\) a \(t\) è un flusso di valore ammissibile \(k\): ogni arco porta al massimo \(1\), e ogni percorso entra ed esce dai suoi nodi interni. Quindi \(k \le \tilde{v}\).

2. I flussi danno percorsi. Per Corollario 5.10 esiste un flusso \(\vet{x}\) con \(x_{ij} \in \{0,1\}\) e valore \(\tilde{v}\). Se \(\tilde{v} \ge 1\), camminare da \(s\) lungo gli archi con \(x_{ij}=1\), ciascuno utilizzato al massimo una volta, finché non viene raggiunto \(t\):

   • in un nodo \(i \notin \{s,t\}\) il cammino ha utilizzato un arco in entrata in più rispetto agli archi in uscita, e la conservazione dà un arco di uscita inutilizzato con flusso;

   • a \(s\) il cammino ha utilizzato tanti archi in uscita quanti in entrata, mentre gli archi con flusso in uscita da \(s\) sono \(\tilde{v} \ge 1\) più di quelli che entrano: ne esiste uno inutilizzato.

   La passeggiata termina, in \(t\), e contiene un percorso \(P\) da \(s\) a \(t\) (Capitolo 1, Lemma «una passeggiata contiene un cammino»). L'impostazione di \(x_{ij}=0\) su \(P\) lascia un flusso \(0/1\) di valore \(\tilde{v}-1\); ripetendo fornisce percorsi \(\tilde{v}\) arcodisgiunti.

3. Rimozione archi. Se la rimozione di un set \(F\) di archi non lascia alcun percorso da \(s\) a \(t\), il set \(S\) dei nodi ancora raggiungibile da \(s\) ha \(t \notin S\) e \(\delta^+(S) \subseteq F\), quindi \(|F| \ge u(S,N \setminus S) \ge \tilde{v}\). Viceversa, ogni percorso da \(s\) a \(t\) lascia \(S\) attraverso un arco di \(\delta^+(S)\): rimozione del \(\tilde{v}\) archi in avanti di un taglio minimo (Teorema 5.8) non lasciano alcun percorso. □

Esempio 5.10: percorsi arcodisgiunti nel grafo di riferimento

Sul grafo di riferimento con tutte le capacità \(1\), \(s=1\) e \(t=6\), l'algoritmo Edmonds–Karp trova i percorsi \(1,2,4,6\) e \(1,3,5,6\) e \(\tilde{v}=2\). Questi due percorsi sono archi disgiunti e rimuovendo i due archi \((1,2)\), \((1,3)\) lasciando il nodo \(1\) non lascia alcun percorso da \(1\) a \(6\): entrambi i numeri di Teorema 5.18 sono \(2\).

Una corrispondenza massima di un grafo bipartito è un flusso massimo intero in una rete con capacità unitaria, e lo sono anche i percorsi arcodisgiunti da \(s\) a \(t\); il taglio minimo certifica entrambi.

5.8 Errori tipici

Attenzione

• Conteggio degli archi all'indietro di un taglio. La capacità \(u(S,N \setminus S)\) somma solo gli archi di \(S\) a \(N \setminus S\).

• Dimenticando gli archi all'indietro della rete residua. Solo con gli archi in avanti, il metodo può fermarsi a portata non massima, pari al valore \(5\) sulla rete di riferimento.

• Dando ad un arco all'indietro la capacità \(u_{ij}\). L'arco all'indietro \((j,i)\) ha \(r_{ji}=x_{ij}\): solo il il flusso già inviato può essere rinviato.

• Prendere il collo di bottiglia dalle capacità. Il collo di bottiglia è la capacità residua più piccola \(r_{ij}\) sul percorso, non il più piccolo \(u_{ij}\).

• Aggiungendo \(\delta\) su un arco all'indietro. Lungo un arco all'indietro \((j,i)\) il flusso \(x_{ij}\) diminuisce di \(\delta\).

• Lettura del taglio dagli archi saturati. Il taglio minimo è dato dai nodi raggiungibili da \(s\) in la rete residua alla fermata; non è necessario che gli archi saturati formino un taglio.

• Chiamata del polinomio Ford–Fulkerson. Il suo numero di aumenti può crescere con le capacità, come \(2M\) in Esempio 5.7; Edmonds–Karp produce al massimo \(n\,m\).

5.9 In sintesi

In sintesi

• Un flusso ammissibile rispetta le capacità e si conserva nei nodi diversi da \(s\) e \(t\); il suo valore è il deflusso netto di \(s\) ed è uguale al flusso netto attraverso ogni taglio \(s\)–\(t\).

• Dualità debole: \(v \le u(S,N \setminus S)\) per ogni flusso e ogni taglio.

• La rete residua ha archi avanti con \(r_{ij}=u_{ij}-x_{ij}\) e archi indietro con \(r_{ji}=x_{ij}\); un il percorso aumentante aumenta il valore tramite il collo di bottiglia \(\delta\).

• Taglio minimo flusso massimo: un flusso è massimo se e solo se non esiste alcun percorso aumentante e \(\tilde{v}\) è uguale al capacità di taglio minima; con capacità intere si ha una portata massima intera.

• Ford–Fulkerson (ricerca approfondita): con capacità intere al massimo degli aumenti \(\tilde{v}\), pseudopolinomiale. Edmonds–Karp (ricerca in ampiezza): al massimo aumenti \(n\,m\), tempo \(O(n\,m^2)\).

• Gli abbinamenti massimi nei grafi bipartiti e nei percorsi arcodisgiunti sono flussi massimi interi.

La rete di riferimento in sintesi.

capacità, \(s=1\), \(t=6\)	\(\vet{u}=(5,4,3,2,4,2,4,2,3)\)
portata massima (unico)	\(\tilde{\vet{x}}=(3,4,3,0,4,0,4,1,3)\), \(\tilde{v}=7\)
tagli minimi, capacità \(7\)	\(S=\{1,2\}\), \(\{1,2,3\}\), \(\{1,2,3,4,5\}\)
Ford–Fulkerson (DFS) e potenziamenti \(5\), \(\delta=2,1,2,1,1\)
Edmonds–Karp (BFS) e potenziamenti \(3\), \(\delta=3,3,1\)
tutte le capacità \(1\) e percorsi ad arco disgiunto \(1,2,4,6\) e \(1,3,5,6\)

---

Esercizi su questo capitolo: Flusso massimo