c(e₁) c(e₂) c(e_m)

(m = |E|). Poni E(T) = E' = F e j = 1

Step 2 - Se E' non contiene cicli aggiungi e_j ad E';

j := j+1

Step 3 - Se T = (V,E') è connesso STOP, altrimenti vai

al passo 2

Algoritmo MST-2 (Prim)

Step 1 - Scegli un vertice qualunque v di G come

radice  di T; poni V' = ; per ogni vertice w diverso da v poni l(w) =    c() (se non esiste poni l(w) = ); E' := F

Step 2 - Trova un vertice w V\V' con l(w) minimo e

sia e un lato che connette w a V' di costo pari

a l(w); aggiungi e ad E' e w a V'

Step 3 - " w' V' poni l(w') := min ) }

Step 4 - Se V' = V STOP, altrimenti vai al passo 2

Complessità di MST-2

n-1 iterazioni ciascuna con due operazioni:

operazione A: trova un'etichetta l(w) minima

" w V\V' < n confronti

operazione B: quando w è inserito in V' confronta

il costo di con  l(w') < n confronti

QUINDI: n + (n-1)(n+n) ovvero O(n²) operazioni

ARBORESCENZA DI COSTO MINIMO

DEFINIZIONE un' arborescenza è un albero che connette tutti i nodi di G, orientato a partire da un nodo radice verso tutti gli altri nodi (o viceversa)

INPUT digrafo G = (N,A)

c(a) costo dell'arco a

radice r N

OUTPUT un arborescenza T radicata in r di costo

minimo che connetta tutti i nodi di G

PROPRIETA' in un'arborescenza diretta dalla radice

verso gli altri nodi il grado entrante in ogni nodo

diverso dalla radice è uguale ad 1

FORMULAZIONI  Sia B_j l'insieme di archi entranti

nel nodo j (j r) e sia E l'insieme di paia di nodi tra cui esiste almeno un arco di G. Il problema è trovare un sottoinsieme T di A tale che: (1) nel grafo (N,E) identifichi un sottoinsieme S di E senza cicli; (2) |T B_j| = 1 " j r; (3) il costo c(T) sia il più piccolo possibile.

Per esercizio si trovi una formulazione del problema come PLI a variabili binarie x_ij (=1 se l'arco (i,j) appartiene a T, =0 altrimenti).

Algoritmo (di Edmonds-Bock) O(n²)

k:=1; D_k:=D; S:=F

1.       foreach nodo u, u r, S:=S dove a_u è un arco di valore minimo entrante in u;

2.       if S non contiene cicli go to 5 else sia C un ciclo di S;

3.       [si costruisce un nuovo grafo D' che non contiene i nodi di C, ma contiene un nuovo nodo h=n+k e tutti gli altri nodi di D_k]

foreach arco (i,j) di D_k do

if i,j C then (i,j) A(D');

if i C , j C then D' contiene l'arco (h,j);

if i C , j C then D' contiene l'arco (i,h)

enddo;

if k,l h then w'_kl=w_kl else if k=h then

w'_kl=min_{i C} w_il else if l=h then w'_kl=min dove a_j è l'arco di C che entra nel nodo j;

k:=k+1; D_k:=D'; w:=w'

go to 1;

4.       do until k=1

sia (i,j) l'arco corrispondente in D_k-1 all'arco (i,h) di D_k contenuto in S e sia (l,j) l'arco di

D_k-1 entrante nello stesso nodo j nel ciclo C che ha dato origine al nodo h;

S:=S C\;

cancellare h e sostituire (i,h) con (i,j) in S;

k:=k-1

enddo

5. output S

2-CAMMINI MINIMI

INPUT  un digrafo G = (V,A);

una funzione che assegna una lunghezza c(a) intera non-negativa ad ogni arco a di G;

un vertice speciale s

OUTPUT  la lunghezza l(v) di tutti i cammini più corti da s a tutti gli altri vertici v di G

Algoritmo SP (Dijkstra)

Step 1 " v V\ poni l(v) := c((s,v)) (se (s,v) non esiste poni l(v) := ); V':= ; A':= F

Step 2 determina un vertice w V\V' con l(w) minima; sia v un vertice di V' tale che l(w)= l(v)+c((v,w)); aggiungi (v,w) ad A' e w a V'

Step3  " w' V' per cui (w,w') in G poni l(w')=min

Step 4 se V'=V STOP altrimenti vai a Step 2

Esercizio dimostrare che la complessità di SP è la stessa di MST-2 e cioè O(n²). I due algoritmi differiscono solo in un punto: quale ?

NOTA BENE: l'algoritmo SP non funziona quando

gli archi hanno costi anche negativi; infatti in tal

caso il problema non è ben definito dovendosi

specificare se è permesso oppure no di passare più

volte dallo stesso vertice (cioè se si vuole cammini

semplici solamente o no). Il problema resta

risolubile in tempo polinomiale se si sa a priori che

G non contiene cicli di lunghezza totale negativa, ma

l'algoritmo per risolverlo è il seguente di complessità

O(n³) (dimostrare per esercizio):

Algoritmo FORD 

for each j V do   

begin

l(j) :=

p(j) := -1

end ; l(s) := 0;

for i := 1 to n do

begin

for j := 1 to n do

begin

h l(k) + c((k,j))

:= min ;

if h < l(j) then do

begin

l(j) := h

p(j) := k

end

end

end

output i vettori l e p

3-ACCOPPIAMENTI OTTIMI

DEFINIZIONE Un sottoinsieme M dei lati di un grafo

G = (V,E) è un accoppiamento se ogni vertice di G è incidente al più ad un lato di M. Un accoppiamento si dice perfetto (o completo) se ogni vertice appartiene ad esattamente un lato di M.

APPLICAZIONI

1.       Sia S un insieme di elementi e siano assegnati k sottoinsiemi di S. Trovare k differenti elementi di S tali che l'elemento j appartenga al j-esimo sottoinsieme.

2.       Un insieme di lavori deve essere eseguito da altrettanti addetti. Ogni addetto è capace di eseguire solo un sottoinsieme dato dell'insieme di lavori. Assegnare un addetto al massimo numero di lavori possibile. L'abilità di ogni potenziale addetto se assegnato ad un certo lavoro può essere misurata da un'opportuna quantità: in tal caso si cerca l'assegnamento di lavori ad addetti che massimizzi un'assegnata cifra di merito funzione delle quantità date.

CAMMINI ALTERNANTI E AUMENTANTI

DEFINIZIONE  Un cammino alternante in un grafo G = (V,E) rispetto ad un accoppiamento M è un cammino ( v₁, . , v_k ) dove tutti i lati ,, . ,, . sono in M oppure sono in M i lati ,, . ,, . Cioè lati di M si alternano con lati di E\M nel cammino.

DEFINIZIONE  Un cammino aumentante è un cammino alternante nel quale entrambi i vertici terminali sono "liberi" (= non incidenti a lati di M).

NOTA BENE: se esiste un cammino aumentante P in G rispetto all'accoppiamento M allora si può ottenere un accoppiamento di cardinalità maggiore eliminando da M i lati di P M ed aggiungendovi i lati di P\M.

TEOREMA    Un accoppiamento M in un grafo G = (V,E) è di cardinalità massima se e solo se non esistono cammini aumentanti P in G rispetto ad M.

DIMOSTRAZIONE    Abbiamo già visto che se P esiste allora M non è di cardinalità massima e quindi resta solo da dimostrare che se M non è di cardinalità massima esiste sempre un cammino aumentante P. Sia M' un accoppiamento di cardinalità maggiore di M in G e si consideri la differenza simmetrica dei due insiemi M ed M': D := (M'\M) (M\M') = M' M. Nel grafo G'= (V,D) dato che ogni vertice è incidente al più ad un lato di M e ad uno di M', tutti i vertici hanno grado 0,1 o Dato che tutti i vertici di grado 2 sono incidenti ad un lato di M ed a un lato di M', tutte le componenti connesse di G' sono o cammini alternanti o cicli alternanti. Ma dato che M' è di cardinalità maggiore di M, esiste almeno un cammino P contenente più lati di M' che di M: P è un cammino alternante con entrambi i vertici terminali non incidenti a lati di M e quindi è un cammino aumentante

Questo teorema suggerisce naturalmente per trovare un accoppiamento di cardinalità massima il seguente

Algoritmo MM

Step 1 M := F

Step 2 trova un cammino aumentante P in G

rispetto ad M se esiste altrimenti STOP

Step 3 M := (M\(M P)) (P\M); torna al passo 2

L'algoritmo MM è in effetti incompleto finché non si dica come trovare P al passo 2: riportiamo qui di seguito un algoritmo polinomiale per fare ciò nei grafi bipartiti, ma che non funziona se applicato a grafi qualunque. Sia G un grafo bipartito: indichiamo con V e W le due "sponde" di vertici e con E l'insieme dei suoi lati.

Algoritmo APM

Step 1 Etichetta con "no" tutti i vertici di W e tutti i vertici di V incidenti a lati di M; etichetta con "si" tutti i vertici di V non accoppiati; sia S l'insieme di questi ultimi vertici e T l'insieme dei vertici di W aventi etichetta "si" (cioè per adesso l'insieme vuoto)

Step 2 Assegna etichetta "si" a tutti quei vertici di W aventi etichetta "no" che sono connessi a un vertice v di S tramite un lato non appartenente ad M; aggiungi tutti questi vertici a T e poni S uguale all'insieme vuoto

Step 3 Se uno qualunque dei vertici w di T non è accoppiato allora abbiamo trovato P; altrimenti tutti i vertici di V con etichetta "no" connessi ad un vertice w di T con un lato di M ottengono etichetta "si" e vengono aggiunti ad S; T := F

Step 4 STOP se P è stato trovato oppure se S è vuoto, altrimenti vai al passo 2

GENERALIZZAZIONI

A.       Grafi qualunque: c'è bisogno di un'etichettatura molto più complicata (Edmonds '65)

B.       Caso pesato: trovare un accoppiamento di peso massimo. Se G è bipartito si può usare il metodo ungherese (Kuhn '5?) oppure risolvere il problema trasformandolo semplicemente in uno di flusso di costo minimo (vedi più oltre). Se G non è bipartito si può usare l'algoritmo blossom (Edmonds '65) di complessità O(n³)

C.       Un accoppiamento perfetto può anche definirsi come un sottografo con gradi tutti uguali ad 1. Una generalizzazione è quindi quella di imporre gradi x diversi da 1. Il problema si riconduce al precedente sostituendo ad ogni vertice di G un grafo bipartito completo avente una sponda di cardinalità pari al grado d del vertice in G, l'altra di cardinalità pari a d-x e inserendo i lati di G fra nodi delle sponde più numerose. Naturalmente questa trasformazione è molto inefficiente ed esistono algoritmi ad-hoc

D.       Se si vuole trovare un cammino di lunghezza minima in un grafo non-orientato con lati di costo negativo, ma senza cicli negativi, non possiamo sostituire ad ogni lato due archi in sensi opposti dello stesso costo, come si può nel caso di costi tutti positivi perché si creano cicli di costo totale negativo e nessuno degli algoritmi visti in precedenza può funzionare. Invece si può trasformare il problema in una versione pesata del problema di cui al punto C

PROBLEMA DEL POSTINO (CINESE)

(un applicazione del problema dell'accoppiamento non-bipartito ottimo)

INPUT un grafo connesso G = (V,E) e una funzione che assegna ad ogni lato e un costo non-negativo c(e)

OUTPUT  un sottoinsieme S di lati di G da aggiungere ad E di costo totale minimo tale che il grafo G' = (V,E S) sia Euleriano (cioè sia possibile partire da un vertice qualunque e transitare da ogni lato una volta ed una sola tornando al vertice di partenza, percorrendo ciò che appunto si indica come ciclo Euleriano e che corrisponde a quello che un postino deve fare per consegnare la posta lungo ogni strada della zona a lui assegnata)

TEOREMA (Eulero 1736) Un (multi)grafo G è Euleriano se e solo se è connesso e tutti i suoi vertici hanno grado pari

OSSERVAZIONI    (a) l'insieme di vertici di grado dispari V' in G ha cardinalità pari; (b) tutti i vertici di V' devono avere grado dispari nel grafo (V,S) mentre i rimanenti vertici devono avere grado pari affinché, per il teorema precedente, il grafo risultante sia Euleriano; (c) (V,S) non contiene cicli dato che potrebbero essere eliminati senza aumentare il costo di S e continuando a soddisfare al teorema, nel senso di lasciare inalterata la parità dei vertici; (d) allora S è un insieme di cammini che connettono paia di vertici di V'.

Algoritmo CP

Step 1 Trova tutti i vertici di grado dispari V' di G

Step 2 Determina i cammini minimi fra tutte le coppie di vertici di V'

Step 3 Costruisci il grafo completo H con vertici V' dove il peso di un lato è uguale alla lunghezza del cammino minimo tra v e w in G (determinata al passo precedente)

Step 4 Trova un accoppiamento perfetto M di peso totale minimo in H

Step 5 Per ogni lato di M ricostruisci il corrispondente cammino minimo e aggiungi i suoi archi a G (duplicandoli) ottenendo un multigrafo G'

Step 6 Trova un ciclo Euleriano in G'

Complessità    O(n) + O(|V'|³) O(n³)

4-PROBLEMA DEL FLUSSO MASSIMO

Input   - digrafo G=(N,A) con n nodi e m archi

- nodo di origine s e di destinazione t

- capacità c(a) (intera) positiva per ogni arco  

a di A

Output matrice X=[x_ij] di valori del flusso associato a ciascun arco (i,j) tale che

0 x_ij c_ij  "(i,j) A (1)

S_i=1,.,nx_ij - S_k=1,.,nx_jk = 0 se j s,t

= v se j=t (2)

= -v se j=s

con valore totale del flusso v massimo

DEFINIZIONE 1 un arco (i,j) è detto saturo se x_ij=c_ij

DEFINIZIONE 2 un arco (i,j) con x_ij=0 si dice scarico

DEFINIZIONE 3 sia P un cammino non-orientato da s a t (cioè un cammino ottenuto ignorando la direzione degli archi). Un arco (i,j) in P diretto da s a t si dice in avanti, mentre si dice a ritroso nel caso contrario. P è un cammino aumentante (sottinteso del valore del flusso v) rispetto ad X se tutti i suoi archi in avanti non sono saturi e tutti quelli a ritroso non sono scarichi.

DEFINIZIONE 4 un (s,t)-taglio è identificato da un insieme S N tale che s S e t T=N\S (l' insieme complemento di S rispetto ad N). La capacità del taglio (S,T) è data da

c(S,T) = S_{i S} S_{j T} c_ij  (3)

LEMMA 1 per ogni (s,t)-taglio (S,T)

v = S x_ij - S x_ij (4)

(i,j) F_S    (i,j) B_S

dove F_S è l'insieme di archi in avanti e B_S quello degli archi a ritroso del taglio (S,T).

Dimostrazione dalla (2) v = S S x_ij - S x_jk )

j T i=1,.,n k=1,.,n

cioè

v = S [ S x_ij + S x_ij - S x_jk - S x_jk ]

j T i S    i T k S k T

= S [ S (x_ij - x_ji ) + S (x_ij - x_ji ) ]

j T i S i T

= S S (x_ij - x_ji ) = S x_ij - S x_ij

j T i S    (i,j) F_S    (i,j) B_S

LEMMA 2 per ogni (s,t)-taglio (S,T) e flusso X ammissibile di valore v,

c(S,T) v. (5)

Dimostrazione dalla (4) e dalla (1)

v =   S x_ij - S x_ij S c_ij - 0

(i,j) F_S (i,j) B_S i S,j T

TEOREMA 1 (del cammino aumentante) il valore v del flusso X è massimo se e solo se non esistono cammini aumentanti da s a t rispetto ad X.

Dimostrazione (la parte "solo se" è ovvia) sia X un flusso che non ammette cammini aumentanti da s a t ed S l'insieme di nodi che ammettono un cammino aumentante con origine in s. Allora per tutti gli indici j S e k T si ha che tutti gli archi (j,k) sono saturi oppure tutti gli archi (k,j) sono scarichi. Dal Lemma 1, v = c(S,T) e dal Lemma 2 v deve essere massimo.

TEOREMA 2 (del flusso intero) se tutte le capacità c_jk sono intere, esiste un flusso ammissibile X intero di valore massimo.

Dimostrazione supponendo di iniziare con un flusso nullo e di trovare successivamente gli opportuni cammini aumentanti, il flusso dei vari archi viene sempre aumentato di una quantità intera, arrivando quindi ad una soluzione ottima data dalla matrice X con componenti tutte intere. 

TEOREMA 3 (del massimo flusso e minimo taglio) il valore massimo di un flusso da s a t è uguale alla capacità di un (s,t)-taglio di capacità minima.

Dimostrazione il risultato segue dai Teoremi 1 e 2 e dlla (5) per tutte le reti con capacità dsate da numeri razionali, fatta eccezione (a rigore) per il fatto che ancora dobbiamo dimostrare che ogni rete ammette un flusso massimo: questo fatto viene dimostrato dall'esistenza dell'algortimo MAXFLOW riportato più oltre. 

Osservazione: la versione di MAXFLOW riportata in seguito fa uso di un grafo incrementale. Da ogni arco (i,j) di A possono originarsi al massimo due archi di tale grafo: a⁺= (i,j) se x_ij < c_ij e a^-= (j,i) se x_ij > 0. Ad ogni arco del primo tipo si associa (se richiesto) una lunghezza pari a c_ij - x_ij mentre ad ogni arco del secondo tipo si associa una lunghezza pari ad x_ij. Per evitare situazioni ambigue, il grafo di partenza non deve contenere coppie di archi uno in un senso ed uno in senso opposto fra gli stessi nodi. Se questo accadesse basta inserire un nuovo nodo fittizio h a metà di uno dei due archi in questione che viene quindi sdoppiato in due archi in serie (i,h) e (h,j) entrambi della stessa capacità dell'arco (i,j).

Procedure MAXFLOW (N,A,s,t,C,X,v):

1.       A F

2.       foreach (i,j) A

3.       if x_ij < c_ij then do

4.       A := A l_ij := TRUE ; l_ij:=c_ij-x_ij ;

enddo ;

5.       if x_ij > 0 then do

6.       A := A l_ij := FALSE ; l_ij:=x_ij ;

enddo ;

7.       AUGPATH (N,A,s,t,l,P) ;

8.       if P=F then output X,v [optimum] else do

9.       e := min ;

10.    foreach (i,j) P if l_ij then x_ij:=x_ij+e

else x_ij:= x_ij + e

11.    v:=v+e

12.    MAXFLOW (N,A,s,t,C,X,v)

Osservazioni

• Se G contiene archi non orientate è spesso possibile sostituirli con archi della stessa capacità uno da ia j e uno da j ad i.
• Se anche i nodi di G sono capacitati, si può ricondursi al caso di capacità assegnate solo agli archi introducendo al posto del nodo i due nodi i' e i" con l'arco (i',i") di capacità pari a quella del nodo i.
• Se si vuole un flusso di valore assegnato v* basta aggiungere il nodo t* e l'arco (t,t*) di capacità v*.

COMPLESSITA' DI MAXFLOW

Dipende ovviamente da come viene realizzata la subroutine AUGPATH.

1.       Se si sceglie un qualunque cammino da s a t nel grafo incrementale, l'algoritmo può addirittura non essere polinomiale.

2.       Sembra promettente l'idea di cercare il cammino che assicura il massimo incremento di flusso: ciò si ottiene cercando nel grafo incrementale un cammino da s a t avente lunghezza dell'arco di lunghezza minima, massima. Una semplice modifica dell'algoritmo di Dijkstra risolve questo problema in O(n²).

3.       La terza opzione è quella di scegliere un cammino da s a t con il minor numero di archi, indipendentemente dalla loro lunghezza. Ciò può farsi in O(m).

Nel caso 2 MAXFLOW avrà una complessità O(n²log v) mentre nel caso 3 diventa O(m²n) (Edmonds & Karp 1972).

5- FLUSSO DI COSTO MINIMO

Formulazione:

min S d_ijx_ij

(i,j) A

con i vincoli 0 x_ij c_ij

S_i=1,.,n x_ij - S_k=1,.,n x_jk = 0 se j s,t

= v se j=t

= -v se j=s

dove d_ij è il costo unitario di flusso sull'arco (i,j)

GRAFO INCREMENTALE

Da ogni arco a=(i,j) di A possono nascere al più due archi del grafo incrementale: uno diretto come a di costo d(a) e uno diretto in senso opposto di costo -d(a). Il primo se a non è saturo, il secondo se a non è scarico.

Il costo di un cammino da s a t nel grafo incrementale è dato dalla somma dei costi dei suoi archi e lo stesso vale per i cicli (semplici).

TEOREMA 4 Un flusso X di valore v è di costo minimo se e solo se non ammette cicli di costo strettamente negativo nel corrispondente grafo incrementale.

TEOREMA 5 Aumentando un flusso v di costo minimo di una quantità d tramite un cammino aumentante P di costo minimo fornisce un flusso di valore v+d ancora di costo minimo.

Dimostrazione Per il Teorema 4 non devono esistere cicli di costo negativo né prima né dopo l'aumento di flusso. Per assurdo supponiamo ne esista uno C dopo tale aumento. Allora esso deve contenere almeno un arco b=(i,j) di P. Ma allora l'insieme di archi P C\ deve contenere un cammino aumentante di costo strettamente inferiore a quello di P, che non sarebbe stato un cammino di costo minimo.

Un poco di storia del Flusso di Minimo Costo

Anno    Autore(i) Complessita'

1961    Busacker & Gowen < n³ C

1967    Klein < n³ C

1972    Edmonds & Karp mn² logC

1980    Rock mn²(log n) logD

1984    Tardos m⁴

1984    Orlin m²(log n)(m+n log n)

1985    Fujishige m³(log n)

1986    Galil & Tardos n²(log n)(m+n log n)

1987    Goldberg & Tarjan log(nD)min

dove    D massimo costo

C massima capacità

m numero archi

n numero nodi

Metodi Semplificati (pseudo-polinomiali)

1 Repeat aumentare v cercando ad ogni iterazione il

cammino s-t di costo minimo nel grafo

incrementale.

O(n³C)

2  Repeat   nella rete formata dagli archi di costo

nullo del grafo incrementale, trovare un

flusso massimo; aggiornare flussi e costi.

O(n²D m log n)

3  trovare il flusso massimo (con MAX FLOW)

Repeat    trovare ciclo di costo negativo nel grafo

incrementale; cambiare i flussi (almeno un arco diventa saturo).

O(nm log n + mC n³)

Applicazioni del Flusso di Costo Minimo

Problema di Trasporto

Nei problemi di trasporto si ha un insieme di nodi "sorgente" S, un insieme di nodi di "destinazione" D, e un insieme di nodi di "transito" T. Il flusso totale uscente da un nodo i di S non può essere maggiore di a_i , quello entrante in un nodo j di D non può essere maggiore di b_j , mentre il flusso totale entrante in un nodo di T è sempre uguale a quello uscente. Perché il problema sia ammissibile la sommatoria degli a_i deve essere non inferiore a quella dei b_j . Tale problema si trasforma in uno di Flusso di Costo Minimo aggiungendo: un nodo sorgente s con archi verso tutti i nodi di S di capacità a_i e costo nullo, un nodo destinazione t a cui si arriva da tutti i nodi di D con archi di capacità b_j e costo nullo.

Problema di Assegnamento

Nella versione classica è il problema di assegnare n lavori a n operatori a costo totale minimo (o profitto massimo). I vincoli esprimono il fatto che ogni lavoro deve essere assegnato ad un solo operatore e che un operatore può essere assegnato ad un solo lavoro. E' facile vedere che anche questo problema è un particolare problema di flusso di costo minimo: in effetti è un problema di trasporto con T=F, S un insieme di nodi rappresentanti gli operatori, D un insieme dello stesso numero di nodi rappresentante i lavori, ogni arco indicante se un operatore può essere assegnato ad un certo lavoro e con quale costo, con gli archi tutti di capacità uguale ad 1.

Cammino Minimo

Basta porre nella formulazione generale le capacità uguali ad 1 ed il valore v del flusso richiesto uguale a n-1. Da notare che il metodo di Dijkstra lavora sul problema duale di quello ottenuto con questa formulazione.