Riprendiamo l`algoritmo di Ford-Fulkerson che risolve il problema

Riprendiamo l’algoritmo di Ford-Fulkerson che risolve il
problema del flusso per vederne una delle innumerevoli
applicazioni
1
Reti di flusso
Astrazione per materiale che “scorre” attraverso gli archi (come liquidi nei tubi).
Una rete di flusso è G = (V, E) = grafo orientato con
due nodi particolari: s = sorgente (senza archi entranti)
t = pozzo (senza archi uscenti).


c(e) = capacità dell’arco e.
10
sorgente
s
capacità
5
15
2
9
5
4
15
15
10
3
8
6
10
4
6
15
4
30
7
t
pozzo
10
2
Flusso
Def. Un flusso s-t è una funzione f: E
R+ che soddisfa:
0  f (e)  c(e)
per ogni e  E:
(capacità)
per ogni v  V – {s, t}:
(conservazione)
 f ( e)   f ( e )


e into v
 f è:
Def. Il valore del flusso
e out of v
v( f ) 
 f (e) .
e out of s
0
2
4
10

4 4
0
5
s
9
0
15
5
0
15
0
4
4
3
8
6
0
capacità
flusso
15
4 0
0
6
15 0
0
4
30
10
7
10
t
0
10
valore = 4
3
Problema del massimo flusso
Problema del massimo flusso. Trovare il flusso s-t di massimo valore.
9
9
2
10
10
4
0
4
5
s
1
15
5
9
15
0
9
8
3
8
10
6
4
capacità
flusso
15
4 0
14
6
15
14
4
30
10
7
0
t
10
10
valore = 28
4
Algoritmo del cammino aumentante
Sia P un cammino semplice s-t in Gf
Augment(f, c, P) {
b  bottleneck(P,f)
foreach e  P {
if (e  E) in G: f(e)  f(e)+ b
else
in G: f(eR)  f(e)- b
}
return f
}
Minima capacità residuale
di un arco di P
Arco in avanti
Arco inverso
Ford-Fulkerson(G, s, t, c) {
foreach e  E f(e)  0
Gf  grafo residuale
while (esiste un cammino aumentante P in Gf) {
f  Augment(f, c, P)
aggiorna Gf
}
return f
}
5
Esempio esecuzione algoritmo di Ford-Fulkerson
G:
0
10
s
0
10
2
0
4
2 0
0
8
3
0
9
4
60
0
10
5
0
10
flusso
capacità
t
valore flusso = 0
Rivediamo l’esempio per capire quale può essere la complessità di tempo;
in particolare:
Come varia il valore del flusso ad ogni iterazione?
Quante iterazioni ci sono?
6
Algoritmo di Ford-Fulkerson
G:
8 X
0
10
s
0
10
2
0
4
2 0
0 8
X
8
3
0
9
4
60
5
0
10
8 X
0
10
flusso
capacità
t
valore flusso = X
0 8
2
4
4
2
8
6
10
3
9
5
10
Gf:
P = s-2-5-t
b=8
s
10
10
Capacità residuale
t
7
Algoritmo di Ford-Fulkerson
2
G:
10 X
8
10
0
10
s
2 X
0
2
3
0
4
8
8
0 2
X
9
4
60
5
0
10
10 X
8
10
t
valore flusso = X
8 10
Gf:
4
4
2
2
8
6
10
10
3
9
5
2
8
P
b=2
2
s
t
8
8
Algoritmo di Ford-Fulkerson
G:
10
10
s
0 6
X
10
2
0
4
2 2
8
8
3
2 8
X
9
4
6X
0
6
5
0 6
X
10
10
10
t
valore flusso = 10
X 16
Gf:
b=6
s
2
4
4
10
2
8
6
10
10
3
7
5
10
t
2
9
Algoritmo di Ford-Fulkerson
2
G:
10
10
s
6 8
X
10
2 X
2
0
3
0 2
X
4
8
8
8
9
4
66
6 8
X
10
5
10
10
t
X 18
valore flusso = 16
2
Gf:
b=2
4
4
6
s
10
2
8
6
4
4
3
1
5
10
6
t
8
Nota: l’arco (3,2) in Gf è un arco indietro: (2,3) è in G, quindi f((2,3))  f((2,3))- b
10
Algoritmo di Ford-Fulkerson
G:
10
10
s
8 9
X
10
2
2 3
X
4
2 0
8 7
X
8
3
X8 9
9
4
66
8 9
X
10
5
10
10
t
valore flusso = 18
X 19
2
2
Gf:
b=1
2
4
8
s
10
2
8
6
2
2
3
1
5
10
8
t
8
11
Algoritmo di Ford-Fulkerson
Dopo altre iterazioni….
G:
10
10
s
9
10
2
3
4
2 0
7
8
3
9
9
4
66
9
10
5
10
10
t
valore flusso = 19
3
2
Gf:
s
1
10
2
7
1
3
9
4
1
9
6
1
5
10
t
9
Non ci sono più cammini aumentanti P in Gf: l’algoritmo termina.
12
Teorema Max-flusso Min-taglio
Teorema del cammino aumentante. Un flusso f è un flusso massimo sse
non ci sono cammini aumentanti.
Teorema max-flusso min-taglio. [Ford-Fulkerson 1956] Il valore del
flusso massimo è uguale al valore del minimo taglio.
13
Scegliere Buoni Cammini Aumentanti
Fare attenzione quando si scelgono i cammini aumentanti.
•
Alcune scelte portano ad algoritmi esponenziali.
•
Buone scelte portano ad algoritmi polinomiali.
•
Se le capacità fossero irrazionali, l’algoritmo potrebbe non terminare!
Obiettivo: scegliere cammini aumentanti in modo tale che:
•
Possiamo trovare cammini aumentanti efficientemente.
•
Poche iterazioni.
Scegliere cammini aumentanti: [Edmonds-Karp 1972, Dinitz 1970]
•
Massima capacità bottleneck (però può richiedere molto tempo).
•
Sufficientemente grande capacità bottleneck.
Complessità: O(m2 log 2C) [Edmonds-Karp 1972, Dinitz 1970]
Altro algoritmo che sceglie cammino con minor numero di archi
14
Soviet Rail Network, 1955
È interessante notare che storicamente il problema del flusso massimo fu introdotto durante
la Guerra Fredda per risolvere quello del minimo taglio. Più precisamente, si intendeva
determinare il minimo numero di “tagli da effettuare” (mediante bombardamenti...) alla rete
ferroviaria sovietica per sconnettere Mosca dal resto dell’URSS.
Reference: On the history of the transportation and maximum flow problems.
Alexander Schrijver in Math Programming, 91: 3, 2002.
15
7.5 Matching Bipartito
Un’applicazione del calcolo del flusso massimo
Matching
Matching.
Input: grafo non-orientato G = (V, E).
M  E è un matching se ogni nodo appare in al più un arco in M.
Problema del max matching: trovare un matching di cardinalità massima.


17
Matching bipartito
Ogni arco ha un estremo in
L e l’altro in R
Matching bipartito
Input: grafo bipartito non orientato G = (L  R, E).
M  E è un matching se ogni nodo appare in al più un arco in M.
Problema del max matching: trovare un matching di cardinalità massima.


1
1'
2
2'
matching
1-2', 3-1', 4-5'
L
3
3'
4
4'
5
5'
R
18
Matching bipartito
Ogni arco ha un estremo in
L e l’altro in R
Matching bipartito
Input: grafo bipartito non orientato G = (L  R, E).
M  E è un matching se ogni nodo appare in al più un arco in M.
Problema del max matching: trovare un matching di cardinalità massima.


1
1'
2
2'
max matching
1-1', 2-2', 3-3' 4-4'
L
3
3'
4
4'
5
5'
R
19
Matching bipartito e flusso
Formulazione in termini di flusso massimo.
Creare un grafo G' = (L  R  {s, t}, E' ).
Orientare tutti gli archi da L a R, e assegnare capacità 1.
Aggiungere sorgente s, e archi di capacità 1 da s ad ogni nodo in L.
Aggiungere pozzo t, e archi di capacità 1 da ogni nodo in R a t.
La cardinalità massima di un matching in G = valore di massimo flusso in G'.





G'
1
1
s
L
1
1'
2
2'
3
3'
4
4'
5
5'
1
t
R
20
Correttezza
Teorema. La cardinalità massima di un matching in G = valore di
massimo flusso in G'.
Dim. 
Dato un matching massimo M di cardinalità k.
Si consideri il flusso f che invia 1 unità lungo ognuno dei k cammini da
s a t che contengono gli archi del matching.
f è un flusso e ha valore k.



G
1
1'
2
2'
3
3'
4
5
1
1
1
1'
2
2'
3
3'
4'
4
4'
5'
5
5'
s
1
t
G'
21
Correttezza
Teorema. La cardinalità massima di un matching in G=valore massimo flusso in G'.
Dim. 
Sia f un flusso massimo in G' di valore k.
Per il teorema di integralità  k è intero e quindi f è 0-1.
Si consideri M = insieme di archi da L a R con f(e) = 1.
– Ogni nodo in L e R partecipa in al più 1 arco in M (conservazione)
– |M| = k: considera taglio (L  s, R  t) (ricorda:
f ( e) 
f (e) v( f ). )



1
1
s
G'
1
1'
1


e out of A
e in to A
1
1'
2
2'
3
3'
2
2'
3
3'
4
4'
4
4'
5
5'
5
5'
t
G
22
Matching bipartito: complessità di tempo
Il tempo è dominato dalla ricerca del massimo flusso.
In questo caso C = n (ogni arco uscente da s ha capacità 1).
Quale algoritmo per il flusso massimo usare per il matching bipartito?
Ford-Fulkerson generico: O(m val(f*) ) = O(mC) = O(mn).
Edmonds-Karp: O(m2 log C ) = O(m2log n).
Algoritmo col minor numero di archi : O(m n1/2).



Matching su grafi non-bipartiti.
La struttura dei grafi non-bipartiti è più complicata, ma
ben nota. [Tutte-Berge, Edmonds-Galai]
Algoritmo di Blossom : O(n4). [Edmonds 1965]
Migliore al momento: O(m n1/2).
[Micali-Vazirani 1980]



23
FINE
24