Maximum flow in planar network
di Alon Itai e Yossi Shiloach
Revised: Daniele Contarino
Università degli studi di Catania
Facoltà di Scienze Matematiche FF. NN.
Corso di laurea in Informatica Magistrale
Executive summary
1. Introduzione
2. Reti planari e grafi planari 3. Algoritmo di Berge
4. Algoritmo di Berge con modifica della capacità (algoritmo M) 5. Ricerca del path sovrastante (algoritmo U)
6. Ricerca del flusso in una rete planare generale (algoritmo G) 7. Conclusioni & References
Introduzione
Che cos’è una rete di flusso?
– Un grafo orientato 𝐺 𝑉, 𝐸 ;
– ∀ 𝑢, 𝑣 ∈ 𝐸 ha una capacità non negativa 𝑐 𝑢, 𝑣 ≥ 0;
– ∃ 𝑠, 𝑡 ∈ 𝑉 definiti rispettivamente come vertice sorgente e vertice pozzo;
– È definita la funzione 𝑓: 𝑉 × 𝑉 → ℝ come flusso in G tale che soddisfi le seguenti proprietà:
• Vincolo di capacità: ∀ 𝑢, 𝑣 ∈ 𝑉, 𝑓 𝑢, 𝑣 ≤ 𝑐(𝑢, 𝑣);
• Antisimmetria: ∀ 𝑢, 𝑣 ∈ 𝑉, 𝑓 𝑢, 𝑣 = −𝑓(𝑣, 𝑢);
• Conservazione del flusso: ∀ 𝑢 ∈ 𝑉 − 𝑠, 𝑡 , 𝑣 ∈𝑉 𝑓 𝑢, 𝑣 = 0;
Introduzione
Dove vengono applicate le reti di flusso?
• Rete elettrica (legge di Kirchhoff) o idrica;
• Rete stradale;
• Studi sulla sicurezza dei flussi di veicoli e di persone;
• Flussi d’aria nelle condutture
Reti planari e grafi planari
Una rete di flusso (G, s, t, c) si dice planare se G è un grafo planare. Un grafo planare è un
particolare grafo che può essere rappresentato su un piano senza che gli archi che congiungono i
vari vertici si intersechino tra di loro.
Esempi di grafi planari.
Reti planari e grafi planari
Esempi di reti planari sono sotto i nostri occhi ogni giorno!
PCB Circuiti elettronici Tracciati stradali
Reti planari e grafi planari
Alcune definizioni
• Sia 𝑃 = (𝑣0, … , 𝑣𝑘) un percorso (path) orientato e 𝑣𝑖−1 → 𝑣𝑖 ∈ 𝐸, 𝑖 = 1 … 𝑘 ;
• P è semplice se tutti i suoi vertici sono distinti;
• Il grafo G è rappresentato da liste di incidenza. Ogni vertice v ha una lista ordinata 𝐸𝑣 che contiene tutti gli archi;
• Sia 𝑃1 (𝑠 = 𝑣0, … , 𝑣𝑘 = 𝑡) e 𝑃2 (𝑠 = 𝑢0, … , 𝑢𝑗 = 𝑡) due path semplici. Diremo che P1 sovrasta P2
Reti planari e grafi planari
se 𝑣𝑖 = 𝑢𝑖, 𝑝𝑒𝑟 𝑖 = 0 … 𝑟, 𝑣𝑟+1 ≠ 𝑢𝑟+1 𝑒 𝑣𝑟 → 𝑣𝑟+1 𝑝𝑟𝑒𝑐𝑒𝑑𝑒 𝑣𝑟 → 𝑢𝑟+1 nell’ordine 𝐸𝑣
• La relazione «sovrasta» è totalmente antisimmetrica per tutto l’insieme dei path semplici.
• Il massimo dei path semplici è l’uppermost path (path
predominante)
Berge’s Algorithm
Claude Berge (5 Giugno1926 – 30 Giugno 2002) fù un matematico francese che sviluppò l’idea che segue nel 1962 e sviluppò
l’algoritmo di cui prende il suo nome.
Berge’s Algorithm
Dato un grafo in cui abbiamo s (la sorgente) e t (il pozzo), possiamo trovare il massimo flusso tramite l’algoritmo di Berge.
L’idea di questo algoritmo è quella di, partendo da un grafo con flusso 0, incrementare
l’uppermost path fino a saturarlo. Dopodiché eliminare il «collo di bottiglia» e reiterare
il procedimento finché s e t non sono scollegati.
L’ultimo uppermost path è il flusso massimo.
Berge’s Algorithm
BERGE-ALGORITHM(G)
i:= 1; E := Get-Edges(G) for each 𝑒 ∈ 𝐸
f0(e) = 0
res(e) = c(e) row2:
Pib = Find-Uppermost-Path(G) if(is_empty(Pib)) return Pi-1b
eib = Find-Bottleneck(Pib) for each 𝑒 ∈ 𝐸
if(𝑒 ∈ 𝑃𝑖𝑏) fib (e) = fi-1b (e) + res(eib) else fib (e) = fi-1b (e)
res(e) = c(e) - fib (e)
Delete-edge(G, eib) i:= i + 1
goto row2
Berge’s Algorithm
La complessità di BERGE-ALGORITHM è 𝑂 𝑛2 , che è migliore rispetto a:
• E
DMONDS-K
ARP𝑂 𝑛𝑚
2• D
INIC𝑂 𝑛
2𝑚
• K
ARZANOV𝑂 𝑛
3Ovviamente il suo campo di azione è limitato alle reti planari.
Berge’s Algorithm
Berge’s Algorithm con capacità modificata
L’algoritmo di Berge ha una complessità di 𝑂 𝑛
2, di seguito viene proposto una variate dove viene
modificata la capacità invece che la capacità
residua.
Tale implementazione avrà una
complessità di 𝑶(𝒏 𝒍𝒐𝒈𝒏)
Berge’s Algorithm con capacità modificata
ALGORITHM-M(G)
| f0M |:= 0; Pib := ∅; i:=1; E := Get-Edges(G)
body:
PiM = Find-Uppermost-Path(G) if(is_empty(PiM))
for each 𝑒 ∈ 𝐸
if(𝑒 ∈ 𝑃𝑖𝑀) fM(e) := 𝑓𝐿 𝑒𝑀 − |𝑓𝐼 𝑒 −1𝑀 | else fM(e) := 0
return fM
for each 𝑒 ∈ 𝑃𝑖𝑀 − 𝑃(𝑖−1)𝑀 M(e) := c(e) + |fiM|
Berge’s Algorithm con capacità modificata
eiM := Find-Bottleneck(PiM)
|fiM|:= M(eiM) := min
𝑒 ∈𝑃𝑖𝑀𝑀(𝑒) Delete-edge(G, eiM)
i := i + 1 goto body
Berge’s Algorithm con capacità modificata
Vediamo alcune equivalenze
Inoltre vengono definiti I(e) e L(e) che sono rispettivamente l’indice del primo e l’ultimo uppermost path a cui e ha partecipato
Berge Algoritmo M
P
iBP
iMe
iBe
iMf
iBf
iMUppermost path
Finora ci siamo concentrato nel trovare il massimo flusso, ma non abbiamo ancora dato un metodo per trovare l’uppermost path.
Un metodo per trovare l’uppermost path è il seguente: sia Pi-1 uppermost path all’instante i-1. Eliminando il collo di bottiglia 𝑣𝑗 → 𝑣𝑗+1 otteremo 2 path (Ps che parte da s e Pt che
arriva a t). Il seguente algoritmo trova Pi
costruendo Ps fino ad incontrare Pt. Per i = 1, Ps = (s) e Pt = (t)
Uppermost path
ALGORITHM-U(G, I)
Pi := Ps; v := vj; row2:
e := Previous-Edge(Pi, v);
row3:
if( Ev = {e} )
if(v = s) return; #no (s,t) path exists
else #Case 6.a
v := Start-Vertex(e) Delete-edge(G, e) goto row2
e’ = succv (e)
if(End-Vertex(e’) = v) #Case 6.b Delete-edge(G, e’)
goto row3
Uppermost path
w := End-Vertex(e’)
if(𝑤 ∉ 𝑃𝑖 ∪ 𝑃𝑡) #Case 6.c Add-edge(Pi, e’)
v := w goto row2
if(𝑤 ∈ 𝑃𝑡) #Case 6.d
Add-edge(Pi, e’)
Delete-edges(Pi, vj+1, w) Add-edges(Pi, Pt, w, t) return
if(𝑤 ∈ 𝑃𝑖) #Case 6.e
Delete-edge(Pi, e’) Delete-edges(Pi, v, w) v := w
goto row2
Trovare un flusso D in una rete planare generale
Si può verificare che ci sia la necessità di trovare un
determinato flusso all’interno di una rete planare. Questo valore 𝐃 ∈ 𝐑
+è il flusso che vogliamo cercare.
Tale algoritmo ha una
complessità 𝑂(𝑛
2log 𝑛)
Trovare un flusso D in una rete planare
ALGORITHM-G(G, D)
P := Get-Shortest-Path(G, s, t);
f := Get-Flow(P, D)
row2:
e0 := Get-Overflowed-Edge(P) if(is-empty(e0))
return P
G’ := (V, E’ = E – {e0, e0’})
if(𝑓 𝑒 > 𝑐(𝑒)) c’(e) := 0
c’(e) else if(𝑐 𝑒 ≥ 𝑓 𝑒 > 0) c’(e) := c(e) – f(e) else c’(e) := c(e) + f(e’)
Trovare un flusso D in una rete planare
N’ := (G’, x, y, c’)
f’ := Get-Flow(N’, f, c, e0) # 𝒇′ = 𝒇 𝒆𝟎 − 𝒄(𝒆𝟎)
if( is-empty(f’) ) return nil;
f’(e0) := |f’|
f := f + f’
goto row2
Conclusioni & References
Conclusioni
• Minore complessità per reti di flusso planari;
• Casistica diffusa;
• Operazioni di base su liste di adiacenza;
References
• Alon Itai and Yossi Shiloach, (1979), Maximum flow in planar network
• Claude Berge and A. Ghouila-Houiri, (1962), Programming, games and transportation networks
Grazie per l’attenzione!
Maximum flow in planar network
Università degli studi di Catania
Facoltà di Scienze Matematiche FF. NN.
Corso di laurea in Informatica Magistrale
