5.2 Tagli¶
Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp
Definizione 5.2: \(s\)–\(t\) taglio
Lascia che \(S \subseteq N\) con \(s \in S\) e \(t \notin S\). Il taglio \(s\)–\(t\) \((S,N \setminus S)\) è il partizione dei nodi in \(S\) e \(N \setminus S\).
-
I suoi archi in avanti sono gli archi di \(\delta^+(S)\), da \(S\) a \(N \setminus S\), e i suoi all'indietro archi gli archi di \(\delta^-(S)\), da \(N \setminus S\) a \(S\).
-
La sua capacità è la capacità totale degli archi anteriori:
\[ u(S,N \setminus S)=\sum_{(i,j) \in \delta^+(S)} u_{ij} . \] -
Un taglio minimo è un taglio \(s\)–\(t\) di capacità minima.
-
Le capacità degli archi indietro non entrano in \(u(S,N \setminus S)\).
-
Ogni nodo diverso da \(s\) e \(t\) può trovarsi su entrambi i lati, quindi una rete ha tagli \(2^{n-2}\) \(s\)–\(t\).
-
Come nel Capitolo 4, \(x(F)=\sum_{(i,j) \in F} x_{ij}\) per un insieme di archi \(F\).
Lemma 5.3: flusso attraverso un \(s\)–\(t\) taglio
Sia \(\vet{x}\) un flusso ammissibile di valore \(v\). Quindi, per ogni \(s\)–\(t\) tagliato \((S,N \setminus S)\),
In particolare, con \(S=N \setminus \{t\}\), la raccolta netta di \(t\) è \(v\).
Dimostrazione
Sia \(b_i\) il deflusso netto del nodo \(i\) sotto \(\vet{x}\): \(b_s=v\) e \(b_i=0\) per \(i \notin \{s,t\}\). Poi \(\vet{x}\) soddisfa la conservazione del flusso con questi equilibri e Capitolo 4, Lemma «flusso attraverso un taglio» dà \(x(\delta^+(S))-x(\delta^-(S))=\sum_{i \in S} b_i\) per ogni \(S \subseteq N\).
-
Con \(S=N\) nessun arco esce o entra in \(S\), quindi \(\sum_{i \in N} b_i=0\) e \(b_t=-v\).
-
Per un taglio \(s\)–\(t\), \(s \in S\) e \(t \notin S\), quindi \(\sum_{i \in S} b_i=b_s=v\). □
Corollario 5.4: dualità debole
Per ogni portata ammissibile \(\vet{x}\) di valore \(v\) ed ogni \(s\)–\(t\) taglio \((S,N \setminus S)\),
con uguaglianza se e solo se \(x_{ij}=u_{ij}\) per ogni \((i,j) \in \delta^+(S)\) e \(x_{ij}=0\) per ogni \((i,j) \in \delta^-(S)\). In case of equality, \(\vet{x}\) is a maximum flow and \((S,N \setminus S)\) è un taglio minimo.
Dimostrazione
Da Lemma 5.3 e i limiti \(x_{ij} \le u_{ij}\) su \(\delta^+(S)\) e \(x_{ij} \ge 0\) su \(\delta^-(S)\),
-
L'uguaglianza vale se e solo se ogni limite utilizzato è stretto, arco per arco.
-
In caso di uguaglianza, ogni flusso ammissibile \(\vet{x}'\) ha valore \(v' \le u(S,N \setminus S)=v\), e ogni \(s\)–\(t\) tagliare \((S',N \setminus S')\) ha \(u(S',N \setminus S') \ge v=u(S,N \setminus S)\).
□
Esempio 5.2: i tagli della rete di riferimento
La rete di riferimento di Esempio 5.1 ha tagli \(2^4=16\) \(s\)–\(t\). Accanto a ciascun set \(S\), il capacità \(u(S,N \setminus S)\):
-
La capacità minima è \(7\), ottenuta con tre tagli: \(S=\{1,2\}\), \(S=\{1,2,3\}\) e \(S=\{1,2,3,4,5\}\). Di Corollario 5.4, nessun flusso ammissibile ha un valore maggiore di \(7\).
-
Per \(S=\{1,2,3\}\) gli archi in avanti sono \((2,4)\), \((3,5)\) e l'arco all'indietro è \((4,3)\). Con il flusso \(\bar{\vet{x}}\) di Esempio 5.1,
\[ \bar{x}_{24}+\bar{x}_{35}-\bar{x}_{43}=3+2-2=3=v, \qquad u(S,N \setminus S)=u_{24}+u_{35}=3+4=7 . \]
La capacità di un taglio
La capacità \(u(S,N \setminus S)\) somma le capacità solo degli archi anteriori. Per \(S=\{1,2,3\}\) sì \(u_{24}+u_{35}=7\); aggiungendo la capacità dell'arco all'indietro \((4,3)\) si otterrebbe \(9\), che non delimita nulla. Un flusso su a L'arco all'indietro riporta le unità in \(S\) e riduce il flusso netto attraverso il taglio.
Il flusso netto attraverso ogni taglio \(s\)–\(t\) è il valore \(v\), quindi \(v \le u(S,N \setminus S)\) per ogni flusso e ogni taglio, con uguaglianza quando gli archi anteriori sono saturi e gli archi posteriori vuoti. Sulla rete di riferimento non c'è flusso valore maggiore di \(7\).
Avanti: 5.3 La rete residua