6.2 Circolazioni e loro scomposizione¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso di costo minimo
Definizione 6.4: circolazione
Sia \(H=(N,F)\) un grafo diretto. Un circolazione su \(H\) è un vettore \(\vet{y} \in \R^{F}\) con \(\vet{y} \ge \vet{0}\) tale che ogni nodo abbia un flusso in uscita uguale all'afflusso:
Il vettore di incidenza \(\vet{\chi}^W\) di un ciclo diretto \(W\) di \(H\), con \(\chi^W_a=1\) sugli archi di \(W\) e \(\chi^W_a=0\) altrove, è una circolazione.
Lemma 6.5: scomposizione in cicli
Sia \(\vet{y} \neq \vet{0}\) una circolazione su \(H=(N,F)\), con archi \(p\) dove \(y_a>0\). Poi ci sono i cicli diretti \(W_1,W_2,\dots,W_k\) di \(H\), con \(k \le p\), composto da archi con \(y_a>0\) e numeri \(\theta_1,\theta_2,\dots, \theta_k>0\) tale che
Se \(\vet{y}\) è un numero intero, i numeri \(\theta_h\) sono numeri interi.
Dimostrazione
Per induzione su \(p\).
-
Un ciclo. Sia \((i_0,i_1)\) un arco con \(y_{i_0i_1}>0\). Il nodo \(i_1\) riceve un afflusso positivo, quindi da bilanciare alcuni archi \((i_1,i_2)\) ha \(y_{i_1i_2}>0\). Proseguendo allo stesso modo costruiamo un cammino diretto formato da archi con \(y>0\). Poiché \(N\) è finito, un nodo si ripete e il tratto di cammino tra le sue due occorrenze è un ciclo diretto \(W_1\).
-
Rimozione. Lascia che \(\theta_1=\min_{a \in W_1} y_a>0\). Il vettore \(\vet{y}'=\vet{y}-\theta_1 \vet{\chi}^{W_1}\) è non negativo, è bilanciato come differenza di vettori bilanciati e ha al massimo \(p-1\) archi positivi, poiché \(y'_a=0\) su un arco di \(W_1\) che raggiunge il minimo.
-
Induzione. Se \(\vet{y}'=\vet{0}\), allora \(\vet{y}=\theta_1\vet{\chi}^{W_1}\). Altrimenti l'induzione dà \(\vet{y}'=\sum_{h=2}^{k}\theta_h\vet{\chi}^{W_h}\) con \(k-1 \le p-1\) cicli di archi con \(y'_a>0\), quindi \(y_a>0\).
Se \(\vet{y}\) è un numero intero, \(\theta_1\) è una delle sue voci e \(\vet{y}'\) è un numero intero, quindi tutti i \(\theta_h\) sono numeri interi. □
Lemma 6.6: la differenza di due flussi fattibili
Siano \(\vet{x}\) e \(\vet{x}'\) flussi ammissibili. Definire \(\vet{y}\) sugli archi di \(G(\vet{x})\): per ogni \((i,j) \in A\),
e \(y=0\) sugli altri archi di \(G(\vet{x})\). Quindi \(\vet{y}\) è una circolazione su \(G(\vet{x})\) con \(y_{ij} \le r_{ij}\), e
per ogni scomposizione di \(\vet{y}=\sum_{h=1}^{k}\theta_h\vet{\chi}^{W_h}\) in cicli di \(G(\vet{x})\).
Dimostrazione
Controlliamo che \(\vet{y}\) viva su \(G(\vet{x})\), che sia bilanciato e il suo costo.
-
Se \(x'_{ij}>x_{ij}\), allora \(x_{ij}<x'_{ij} \le u_{ij}\): l'arco in avanti esiste e \(y_{ij} \le u_{ij}-x_{ij}= r_{ij}\). Se \(x'_{ij}<x_{ij}\), allora \(x_{ij}>x'_{ij} \ge l_{ij}\): esiste l'arco all'indietro e \(y_{ji} \le x_{ij}-l_{ij} =r_{ji}\).
-
Come nella dimostrazione di Proposizione 6.3, \(y\) su un arco \((i,k)\) di \(G(\vet{x})\) aggiunge \(y\) al deflusso meno l'afflusso di \(i\) e lo sottrae da quello di \(k\), esattamente come la variazione da \(\vet{x}\) a \(\vet{x}'\) fa sull'arco corrispondente di \(A\). Quindi il deflusso meno l'afflusso di \(\vet{y}\) nel nodo \(i\) è \((\mat{B}\vet{x}')_i-(\mat{B}\vet{x})_i=b_i-b_i=0\).
-
Un arco in avanti contribuisce \(c_{ij}(x'_{ij}-x_{ij})\), un arco all'indietro \(-c_{ij}(x_{ij}-x'_{ij})=c_{ij}(x'_{ij}- x_{ij})\): il totale è \(\vet{c}'(\vet{x}'-\vet{x})\). Con la scomposizione, \(\sum c^x_{ij}y_{ij}=\sum_h \theta_h \sum_{(i,j) \in W_h} c^x_{ij}=\sum_h \theta_h\, c(W_h)\). □
- Per Lemma 6.5 esiste una tale scomposizione: \(\vet{x}'\) è \(\vet{x}\) aumentata lungo i cicli \(W_1,W_2,\dots,W_k\) di \(G(\vet{x})\) di \(\theta_1,\theta_2,\dots,\theta_k\). Poiché \(\vet{y}\) è positivo su al massimo un arco di \(G(\vet{x})\) per arco di \(A\), \(k \le m\).
Esempio 6.2: dal flusso più costoso al flusso ottimale
Confrontiamo \(\vet{x}^0\) di Esempio 6.1, di costo \(80\), con il flusso ottimale \(\tilde{\vet{x}}=(2,3,4,0,3,0,2,1,2)\) del capitolo 4, di costo \(60\). La differenza è
quindi \(\vet{y}\) è positivo su otto archi di \(G(\vet{x}^0)\): gli archi in avanti \((1,2)\) e \((5,6)\), con \(y=1\), e gli archi all'indietro
Seguiamo la dimostrazione di Lemma 6.5, partendo ogni volta dal primo arco con \(y>0\) in ordine lessicografo e lasciando ogni nodo lungo il suo arco con \(y>0\) di testa più piccola:
| \(h\) | ciclo \(W_h\) | \(\theta_h\) | \(c(W_h)\) |
|---|---|---|---|
| \(1\) | \(1,2,3,1\) | \(1\) | \(2-2-2=-2\) |
| \(2\) | \(3,4,5,3\) | \(1\) | \(-3-5-3=-11\) |
| \(3\) | \(4,5,6,4\) | \(1\) | \(-5+3-5=-7\) |
Di Lemma 6.6, \(\vet{c}'\tilde{\vet{x}}-\vet{c}'\vet{x}^0=-2-11-7=-20=60-80\). Tutto tre cicli sono negativi e \(W_2\) è il ciclo \(4,5,3,4\) di Esempio 6.1, scritto da nodo \(3\).
Una circolazione è una somma di multipli positivi di cicli orientati. La differenza tra due flussi ammissibili è a circolazione su \(G(\vet{x})\): ogni flusso fattibile viene raggiunto da \(\vet{x}\) lungo cicli di \(G(\vet{x})\), e il costo modifiche apportate da \(\sum_h \theta_h\, c(W_h)\).