1
Chapter 7 Network Flow
2
Rete ferroviaria sovietica
Hanno analizzato problemi di trasporto relati alla rete ferroviaria sovietica:
A.N. Tolstoi, Methods of finding the minimal total kilometrage in cargo- transportation planning in space, 1930, (in russo)
T.E. Harris, F.S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955.
Scritto per US Air Force, dapprima “classified” e poi “unclassified” il 21 maggio 1999.
I nodi rappresentano piccole regioni connesse con archi
Capacità di una connessione: tonnellate che possono essere trasportate in un giorno
Interesse degli US: calcolo dei “bottleneck” per disconnettere gli stati satellite
in Math Programming, 91: 3, 2002.
Rete ferroviaria sovietica, 1955
Riferimento: On the history of the transportation and maximum flow problems.
Alexander Schrijver in Math Programming, 91: 3, 2002.
Harris e Ross: Max flow di 163.000 tonnellate dalla Russia all’Europa dell’Est e taglio di capacità 163.000 tonnellate indicato come “The bottleneck”
Altri esempi di network
Liquidi attraverso tubi
Parti tra le linee di assemblaggio
Corrente attraverso una rete elettrica
Informazione in reti di comunicazioni
Trasporto di merci su strada
…
1
Chapter 7 Network Flow
2
Rete ferroviaria sovietica
Hanno analizzato problemi di trasporto relati alla rete ferroviaria sovietica:
A.N. Tolstoi, Methods of finding the minimal total kilometrage in cargo- transportation planning in space, 1930, (in russo)
T.E. Harris, F.S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955.
Scritto per US Air Force, dapprima “classified” e poi “unclassified” il 21 maggio 1999.
I nodi rappresentano piccole regioni connesse con archi
Capacità di una connessione: tonnellate che possono essere trasportate in un giorno
Interesse degli US: calcolo dei “bottleneck” per disconnettere gli stati satellite
in Math Programming, 91: 3, 2002.
Rete ferroviaria sovietica, 1955
Riferimento: On the history of the transportation and maximum flow problems.
Alexander Schrijver in Math Programming, 91: 3, 2002.
Harris e Ross: Max flow di 163.000 tonnellate dalla Russia all’Europa dell’Est e taglio di capacità 163.000 tonnellate indicato come “The bottleneck”
Altri esempi di network
Liquidi attraverso tubi
Parti tra le linee di assemblaggio
Corrente attraverso una rete elettrica
Informazione in reti di comunicazioni
Trasporto di merci su strada
…
1
Chapter 7 Network Flow
2
Rete ferroviaria sovietica
Hanno analizzato problemi di trasporto relati alla rete ferroviaria sovietica:
A.N. Tolstoi, Methods of finding the minimal total kilometrage in cargo- transportation planning in space, 1930, (in russo)
T.E. Harris, F.S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955.
Scritto per US Air Force, dapprima “classified” e poi “unclassified” il 21 maggio 1999.
I nodi rappresentano piccole regioni connesse con archi
Capacità di una connessione: tonnellate che possono essere trasportate in un giorno
Interesse degli US: calcolo dei “bottleneck” per disconnettere gli stati satellite
in Math Programming, 91: 3, 2002.
Rete ferroviaria sovietica, 1955
Riferimento: On the history of the transportation and maximum flow problems.
Alexander Schrijver in Math Programming, 91: 3, 2002.
Harris e Ross: Max flow di 163.000 tonnellate dalla Russia all’Europa dell’Est e taglio di capacità 163.000 tonnellate indicato come “The bottleneck”
Altri esempi di network
Liquidi attraverso tubi
Parti tra le linee di assemblaggio
Corrente attraverso una rete elettrica
Informazione in reti di comunicazioni
Trasporto di merci su strada
…
1
Chapter 7 Network Flow
2
Rete ferroviaria sovietica
Hanno analizzato problemi di trasporto relati alla rete ferroviaria sovietica:
A.N. Tolstoi, Methods of finding the minimal total kilometrage in cargo- transportation planning in space, 1930, (in russo)
T.E. Harris, F.S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, California, 1955.
Scritto per US Air Force, dapprima “classified” e poi “unclassified” il 21 maggio 1999.
I nodi rappresentano piccole regioni connesse con archi
Capacità di una connessione: tonnellate che possono essere trasportate in un giorno
Interesse degli US: calcolo dei “bottleneck” per disconnettere gli stati satellite
in Math Programming, 91: 3, 2002.
Rete ferroviaria sovietica, 1955
Riferimento: On the history of the transportation and maximum flow problems.
Alexander Schrijver in Math Programming, 91: 3, 2002.
Harris e Ross: Max flow di 163.000 tonnellate dalla Russia all’Europa dell’Est e taglio di capacità 163.000 tonnellate indicato come “The bottleneck”
Altri esempi di network
Liquidi attraverso tubi
Parti tra le linee di assemblaggio
Corrente attraverso una rete elettrica
Informazione in reti di comunicazioni
Trasporto di merci su strada
…
5
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
5
6
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
S t
v1
v2
v3
source v4 sink
Rete dei flussi.
Astrazione per flusso materiali sugli archi.
G = (V, E) grafo diretto, senza archi paralleli .
Due nodi distinti: s = sorgente, t = pozzo.
c(e) = capacità dell’arco e.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 capacità
sorgente pozzo
Massimo Flusso e Minimo Taglio
Massimo Flusso e Minimo Taglio.
Due problematiche algoritmiche molto ricche.
Importante problema nell’ottimizzazione combinatoriale.
Bella dualità matematica.
Aplicazioni non banali / riduzioni
Open-pit mining.
Project selection.
Airline scheduling.
Bipartite matching.
Baseball elimination.
Image segmentation.
Network connectivity.
Network reliability.
Distributed computing.
Egalitarian stable matching.
Security of statistical data.
Network intrusion detection.
Multi-camera scene reconstruction.
Many many more . . .
5
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
5
6
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
S t
v1
v2
v3
source v4 sink
Rete dei flussi.
Astrazione per flusso materiali sugli archi.
G = (V, E) grafo diretto, senza archi paralleli .
Due nodi distinti: s = sorgente, t = pozzo.
c(e) = capacità dell’arco e.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 capacità
sorgente pozzo
Massimo Flusso e Minimo Taglio
Massimo Flusso e Minimo Taglio.
Due problematiche algoritmiche molto ricche.
Importante problema nell’ottimizzazione combinatoriale.
Bella dualità matematica.
Aplicazioni non banali / riduzioni
Open-pit mining.
Project selection.
Airline scheduling.
Bipartite matching.
Baseball elimination.
Image segmentation.
Network connectivity.
Network reliability.
Distributed computing.
Egalitarian stable matching.
Security of statistical data.
Network intrusion detection.
Multi-camera scene reconstruction.
Many many more . . .
5
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
5
6
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
S t
v1
v2
v3
source v4 sink
Rete dei flussi.
Astrazione per flusso materiali sugli archi.
G = (V, E) grafo diretto, senza archi paralleli .
Due nodi distinti: s = sorgente, t = pozzo.
c(e) = capacità dell’arco e.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 capacità
sorgente pozzo
Massimo Flusso e Minimo Taglio
Massimo Flusso e Minimo Taglio.
Due problematiche algoritmiche molto ricche.
Importante problema nell’ottimizzazione combinatoriale.
Bella dualità matematica.
Aplicazioni non banali / riduzioni
Open-pit mining.
Project selection.
Airline scheduling.
Bipartite matching.
Baseball elimination.
Image segmentation.
Network connectivity.
Network reliability.
Distributed computing.
Egalitarian stable matching.
Security of statistical data.
Network intrusion detection.
Multi-camera scene reconstruction.
Many many more . . .
5
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
5
6
Network Flow
Un network è un grafo diretto
Archi rappresentano tubi che trasportano liquido
Ogni arco ha una capacità (tubi di grandezze diverse)
Un nodo sorgente
Un nodo pozzo
S t
v1
v2
v3
source v4 sink
Rete dei flussi.
Astrazione per flusso materiali sugli archi.
G = (V, E) grafo diretto, senza archi paralleli .
Due nodi distinti: s = sorgente, t = pozzo.
c(e) = capacità dell’arco e.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 capacità
sorgente pozzo
Massimo Flusso e Minimo Taglio
Massimo Flusso e Minimo Taglio.
Due problematiche algoritmiche molto ricche.
Importante problema nell’ottimizzazione combinatoriale.
Bella dualità matematica.
Aplicazioni non banali / riduzioni
Open-pit mining.
Project selection.
Airline scheduling.
Bipartite matching.
Baseball elimination.
Image segmentation.
Network connectivity.
Network reliability.
Distributed computing.
Egalitarian stable matching.
Security of statistical data.
Network intrusion detection.
Multi-camera scene reconstruction.
Many many more . . .
9
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Taglio
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4
Capacità = 10 + 5 + 15 = 30 A
!
cap(A, B) = c(e)
e esce da A
"
10 s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Taglio
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Capacità = 9 + 15 + 8 + 30 = 62
!
cap(A, B) = c(e)
e esce da A
"
Problema taglio s-t minimo. Trovare un taglio s-t di capacità minima.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Capacità = 10 + 8 + 10 = 28
Flusso
S t
1
2
3
4
Grafo G=(V,E)
S t
1
2
3
4
u 6/12 v
u 6/6 v
f(u,v)=6
f(u,v)=6
Flusso inferiore alla capacità
Massimo flusso
8 3
6
8 6 6
3 3
Esempio: oil pipeline
9
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Taglio
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4
Capacità = 10 + 5 + 15 = 30 A
!
cap(A, B) = c(e)
e esce da A
"
10 s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Taglio
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Capacità = 9 + 15 + 8 + 30 = 62
!
cap(A, B) = c(e)
e esce da A
"
Problema taglio s-t minimo. Trovare un taglio s-t di capacità minima.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Capacità = 10 + 8 + 10 = 28
Flusso
S t
1
2
3
4
Grafo G=(V,E)
S t
1
2
3
4
u 6/12 v
u 6/6 v
f(u,v)=6
f(u,v)=6
Flusso inferiore alla capacità
Massimo flusso
8 3
6
8 6 6
3 3
Esempio: oil pipeline
9
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Taglio
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4
Capacità = 10 + 5 + 15 = 30 A
!
cap(A, B) = c(e)
e esce da A
"
10 s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Taglio
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Capacità = 9 + 15 + 8 + 30 = 62
!
cap(A, B) = c(e)
e esce da A
"
Problema taglio s-t minimo. Trovare un taglio s-t di capacità minima.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Capacità = 10 + 8 + 10 = 28
Flusso
S t
1
2
3
4
Grafo G=(V,E)
S t
1
2
3
4
u 6/12 v
u 6/6 v
f(u,v)=6
f(u,v)=6
Flusso inferiore alla capacità
Massimo flusso
8 3
6
8 6 6
3 3
Esempio: oil pipeline
9
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Taglio
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4
Capacità = 10 + 5 + 15 = 30 A
!
cap(A, B) = c(e)
e esce da A
"
10 s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Taglio
Definizione. Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
Definizione. La capacità di un taglio (A, B) è:
Capacità = 9 + 15 + 8 + 30 = 62
!
cap(A, B) = c(e)
e esce da A
"
Problema taglio s-t minimo. Trovare un taglio s-t di capacità minima.
Problema Taglio Minimo
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
A 4
Capacità = 10 + 8 + 10 = 28
Flusso
S t
1
2
3
4
Grafo G=(V,E)
S t
1
2
3
4
u 6/12 v
u 6/6 v
f(u,v)=6
f(u,v)=6
Flusso inferiore alla capacità
Massimo flusso
8 3
6
8 6 6
3 3
Esempio: oil pipeline
Flusso
S t
1
2 3
4
Grafo G=(V,E) Esempio: oil pipeline
S t
1
2 3
4 8
3
6
6/8 6/6 6/6
3 3
14
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
4
0
0
0
0 0
0 4 4
0
0
0
valore = 4 0
!
f (e)
e entra in v
"
= f (e)e esce da v
"
!
0 " f (e) " c(e)
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
v( f ) = f (e)
eesce da s
"
.4
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
10
6
6
11
1 10
3 8 8
0
0
0 11
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 24
!
0 " f (e) " c(e)
4
!
v( f ) = f (e)
eesce da s
"
.
!
f (e)
e entra in v
"
= f (e)e esce da v
"
Problema Flusso Massimo. Trovare flusso s-t con il massimo valore.
Problema Flusso Massimo
10
9
9
14
4 10
4 8 9
1
0 0
0 14
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 28
Flusso
S t
1
2 3
4
Grafo G=(V,E) Esempio: oil pipeline
S t
1
2 3
4 8
3
6
6/8 6/6 6/6
3 3
14
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
4
0
0
0
0 0
0 4 4
0
0
0
valore = 4 0
!
f (e)
e entra in v
"
= f (e)e esce da v
"
!
0 " f (e) " c(e)
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
v( f ) = f (e)
eesce da s
"
.4
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
10
6
6
11
1 10
3 8 8
0
0
0 11
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 24
!
0 " f (e) " c(e)
4
!
v( f ) = f (e)
eesce da s
"
.
!
f (e)
e entra in v
"
= f (e)e esce da v
"
Problema Flusso Massimo. Trovare flusso s-t con il massimo valore.
Problema Flusso Massimo
10
9
9
14
4 10
4 8 9
1
0 0
0 14
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 28
Flusso
S t
1
2 3
4
Grafo G=(V,E) Esempio: oil pipeline
S t
1
2 3
4 8
3
6
6/8 6/6 6/6
3 3
14
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
4
0
0
0
0 0
0 4 4
0
0
0
valore = 4 0
!
f (e)
e entra in v
"
= f (e)e esce da v
"
!
0 " f (e) " c(e)
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
v( f ) = f (e)
eesce da s
"
.4
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
10
6
6
11
1 10
3 8 8
0
0
0 11
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 24
!
0 " f (e) " c(e)
4
!
v( f ) = f (e)
eesce da s
"
.
!
f (e)
e entra in v
"
= f (e)e esce da v
"
Problema Flusso Massimo. Trovare flusso s-t con il massimo valore.
Problema Flusso Massimo
10
9
9
14
4 10
4 8 9
1
0 0
0 14
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 28
Flusso
S t
1
2 3
4
Grafo G=(V,E) Esempio: oil pipeline
S t
1
2 3
4 8
3
6
6/8 6/6 6/6
3 3
14
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
4
0
0
0
0 0
0 4 4
0
0
0
valore = 4 0
!
f (e)
e entra in v
"
= f (e)e esce da v
"
!
0 " f (e) " c(e)
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
v( f ) = f (e)
eesce da s
"
.4
Definizione. Un flusso s-t è una funzione che soddisfa:
Per ogni e ∈ E: (capacità)
Per ogni v ∈ V – {s, t}: (conservazione) Definizione. Il valore di un flusso è:
Flusso
10
6
6
11
1 10
3 8 8
0
0
0 11
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 24
!
0 " f (e) " c(e)
4
!
v( f ) = f (e)
eesce da s
"
.
!
f (e)
e entra in v
"
= f (e)e esce da v
"
Problema Flusso Massimo. Trovare flusso s-t con il massimo valore.
Problema Flusso Massimo
10
9
9
14
4 10
4 8 9
1
0 0
0 14
capacità flusso s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
valore = 28
17
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )4
A
f (e)
e esce da A! = 10 + 3+11 = 24
f (e)
e entra in A! = 0
v( f ) = 10 + 3+11 = 24
18
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all ammontare che lascia s.
Flussi e Tagli
10
6
6
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
11 A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 6 + 0 + 8 +11 = 25
f (e)
e entra in A! = 1
v( f ) = 10 + 3+11 = 24
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 10 + 8 +10 = 28
f (e)
e entra in A! = 4 + 0 = 4 v( f ) = 10 + 3+11 = 24
Flussi e Tagli
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora,
Prova.
v( f ) = f (e)
e esce da s
!
=
v " A
!
f (e)e esce da v
!
# f (e)e entra in v
!
$
%& '
()
per la conservazione del flusso, tutti i termini eccetto v = s sono 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )Ricorda: Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
17
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )4
A
f (e)
e esce da A! = 10 + 3+11 = 24
f (e)
e entra in A! = 0
v( f ) = 10 + 3+11 = 24
18
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all ammontare che lascia s.
Flussi e Tagli
10
6
6
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
11 A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 6 + 0 + 8 +11 = 25
f (e)
e entra in A! = 1
v( f ) = 10 + 3+11 = 24
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 10 + 8 +10 = 28
f (e)
e entra in A! = 4 + 0 = 4 v( f ) = 10 + 3+11 = 24
Flussi e Tagli
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora,
Prova.
v( f ) = f (e)
e esce da s
!
=
v " A
!
f (e)e esce da v
!
# f (e)e entra in v
!
$
%& '
()
per la conservazione del flusso, tutti i termini eccetto v = s sono 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )Ricorda: Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
17
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )4
A
f (e)
e esce da A! = 10 + 3+11 = 24
f (e)
e entra in A! = 0
v( f ) = 10 + 3+11 = 24
18
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all ammontare che lascia s.
Flussi e Tagli
10
6
6
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
11 A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 6 + 0 + 8 +11 = 25
f (e)
e entra in A! = 1
v( f ) = 10 + 3+11 = 24
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora, il flusso netto inviato attraverso il taglio è uguale all’ammontare che lascia s.
Flussi e Tagli
10
6
6
11
1 10
3 8 8
0
0
0 11
s
2
3
4
5
6
7
t
15 5
30
15 10
8 15 9
6 10
10 10 4 15
4 0 4
A
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f ) f (e)e esce da A! = 10 + 8 +10 = 28
f (e)
e entra in A! = 4 + 0 = 4 v( f ) = 10 + 3+11 = 24
Flussi e Tagli
Lemma valore flusso. Sia f un flusso, e sia (A, B) un taglio s-t. Allora,
Prova.
v( f ) = f (e)
e esce da s
!
=
v " A
!
f (e)e esce da v
!
# f (e)e entra in v
!
$
%& '
()
per la conservazione del flusso, tutti i termini eccetto v = s sono 0
!
f (e)
e esce da A
"
# f (e)e entra in A
"
= v( f )Ricorda: Un taglio s-t è una partizione (A, B) di V con s ∈ A e t ∈ B.
