Max Flow Problem Flashcards
In una rete di flusso come definiamo i flows?
Possiamo definirli in due modi:
1) Flows lungo gli archi
2) Flows lungo percorsi orientati o cicli
Come rappresentiamo flow lungo gli archi?
Sia X un vettore di variabili decisionali con entrante xij,
outflow di i - inflow di i = -e(i) qualcunque i in N.
e(i)<0 -> nodo di deficiti
e(i)>0 -> nodo di eccesso
e(i) =0 -> nodo bilanciato
Flow Decomposition Theorem
Ogni flow di un arco non negativo può essere rappresentanto come il flow lungo un percorso o ciclo orientanto in modo tale che :
1) Ogni percorso orientato con flow positivo connette un nodo di deficit i con nodo di eccesso k.
2) Al più m+n, percorsi diretti o cicli hanno non zero flow , e al più m cicli hanno non zero flow.
Cos’è una rete Residuale?
Una rete residuale si definisce a partire una rete G, sostituitendo ogni arco (i,j) con due archi (i,j) e (j,i): l arco (i,j) ha costo cij e capacità residuale rij=uij-xij e l’arco (j,i) ha costo -cij e rj=xij. Lungo (i,j) il costo aumento e lungo (j,i) decrementa.
Cos’è un augmenting Path?
Ogni percorso diretto dalla sorgente al pozzo nella rete residuale è un agumentin path. Se esiste tale percorso significa che esseno la capacità del aug path sempre positiva che possiamo trasportare una quantitata adddionzale di flow positiva.
Maximum Flow Problem
Il MFP consiste in una rete capacitata nel mandare più flow possibile tra due nodi sorgente e pozzo, senza eccedere la capacità di ciascun arco.
Formulazione LP del MFP
Sia G=(N;A) un grafo orientanto, uij la capacità di ciascun arco e U=max{uij}, A(i) lista delle adiacenze, xij flow lungo gli archi e v l’ammontare di flow trasposrtato da s a t.
Vincoli:
outflow-inflow = v se i=s ,
0 se i in N{s,t}
-v se i = t
Assunszioni nel MFP
1) G è una rete orientanta
2) Tutte le capacità sugli archi sono non negative
3) La rete non possiede percorsi da s a t composti da archi con capacità infinita
4) Se (i,j) in A allora (j,i) in A
Definizione di S-t cut
E’ un taglio tale chs s appartiene all’insieme S e t appartiene ad S(negato)
Cosa si intende per capacità di un s-t cut
E’ il limite superiore sulla quantità di flow mandato da s a t .
Proprietà del s-t cut
Per ogni flow x di valore v in una rete, il flow addizionale che può essere mandanto dalla sorgente al pozzo è minore uguale alla capacità residuale di un qualsiasi s-t cut.
Generic Augmenting Path
L’algoritmo consiste nel individuare la presenza di augmenting path nella rete residuale G(X),aumentare ill flow lungo l’augmentin path finchè la rete non possiede piu questo percorso.
Labeling Algorithm
Performa una ricerca dei nodi che possono essere raggiunti dalla sorgente nella rete residuale G(x). Ad ogni step partiziona i nodi in labeld e unlabeled. I primi sono queli raggiunti dalla sorgente e i secondi quelli ancora non raggiunti. L’algo controlla le lista di adiacenza dei nodi labeled al fine di raggiungere ulteriori nodi. Quando il pozzo viene etichettato manda il max flow possibile da s a t. Elimina tutte le etichette e ricomincia, l’algoritmo termina quando t rimane unlabeled.
Correttezza del Labeling Algorithm
Ad ogni iterazione l algoritmo effettua un augmentation o termina perchè non puo etichettare t. In questo caso,viene determinato un s-t cut[S,S^], per cui la capacità residuale e 0 e il flow corrente eguaglia la capacità del s-t cut. Determiniamo dunque che il flow è massio e il taglio [S,S^] è un taglio di costo minimo.
Max Flow min cut th
Il massimo ammontare di flow in una rete capacitata da un nodo sorgente s a un nodo pozzo t equivale alla capacità minima tra tutti gli s-t cuts.
