Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 17: 11-12 Maggio 2009
- Algoritmo di Kruskal
- Algoritmo di Prim
- Problema del Flusso a Costo Minimo: Formulazione
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Il Problema del Minimo Albero Ricoprente
(Minimum Spanning Tree Problem)
 Si considera un grafo G=(V,E)
 Ad ogni arco ei, i=1,...,n di G è associato un costo ci,
i=1,...,m
Il problema: determinare l’albero ricoprente di G con il
minimo costo associato.
14
4 10
7
Esempio
8
11
9
17
3
2 1 16
12
6
13
5 15
2
Esempi di applicazioni:

determinare la rete di comunicazione più affidabile

determinare la connessione tra n centri a costo
minimo (e.g., distribuzione del gas)
Due algoritmi:

l’algoritmo di Kruskal (Greedy Algorithm)

l’algoritmo di Prim
3
Algoritmo di Kruskal (Minimum Spanning Tree)
(1) E’ dato il grafo G=(V,E) con n nodi ed m archi.
Si ordinano gli archi e1, e2,..., em in modo che i costi
associati non siano decrescenti (c1c2... cm ).
Si pone E0=, k=1 ed il grafo ST0=(V, )
(2) Se (V, Ek-1{ek}) è un grafo aciclico allora STk=(V,Ek)
con Ek=Ek-1{ek}, altrimenti Ek=Ek-1 e STk= STk-1
(3) Se Ek=n-1 l’algoritmo si ferma ed STk è l’albero
ricoprente cercato, altrimenti k=k+1 e continuare col
passo (2).
4
Esempio: n=9 m=17
14
7
4
10
9
17
8
11
12
3
6
2
13
5
1
16
15
5
Algoritmo di Prim (Minimum Spanning Tree)
(1) E’ dato il grafo G=(V,E) con n nodi ed m archi.
Si sceglie un vertice arbitrario di G, V0={vs}, si pone
E0= e k=1
(2) Si connette un nodo viVk-1 con un nodo vhV- Vk-1
tale che il costo dell’arco (vi,vh) sia
c( v i , v h ) 
min
v j Vk  1,v e V  V
( v j,v e )E
c( v j, v e )

k 1
e si pone Vk=Vk-1 {vh} e Ek=Ek-1 {(vi,vh)}
(3) Se Ek=n-1 l’algoritmo si ferma e ST=(Vk,Ek) è
l’albero ricoprente cercato, altrimenti k=k+1 e
continuare col passo (2).
6
Esempio: n=6 m=12
10
9
8
7
12
7.5
17
11
10.5
19
16
9.5
L’algoritmo di Prim O(V|2) è più efficiente di quello di
Kruskal (O(ElogE)).
7
Matrici di Incidenza dei Grafi

Dato G=(V,E) grafo non orientato, AG=[aij], con
i=1,...,n e j=1,...,m è la matrice di incidenza di G,
dove n=V ed m=E, e tale che
1
aij  
0
se vi è testa o coda di e j
altrimenti
8
Esempio
v2
v1
e1
e5
v4
e2
e4
e1 e2 e3 e4 e5
 1 0 0 0 1 v1
0 1 1 0 0 v
 2
e3 A G  
 1 0 1 1 0  v3
 0 1 0 1 1

 v4
v3
matrice di incidenza di un grafo non orientato
9

Dato G=(V,E) grafo orientato, AG=[aij], con i=1,...,n e
j=1,...,m è la matrice di incidenza di G, dove n=V
ed m=E, e tale che
1

aij   1
0

se vi è coda di e j (arco uscente da vi )
se vi è testa di e j (arco entrante in vi )
altrimenti
10
Esempio
v2
v1
e5
v4
e1
e2
e4
e3
e1 e2 e3 e4 e5
 1 0 0 0 1 v1
 0  1 1 0 0 v
2


AG 
 1 0  1  1 0 v 3

v
 0 1 0 1  1 4
v3
matrice di incidenza di un grafo orientato
11
Problema del Flusso a costo Minimo
FORMULAZIONE
n
min
n
 c x
i 1 j 1
ij ij
con vincol i :
n
n
x x
j 1
ij
k 1
ki
 bi
xij  0
i  1,...n
i  1,, n; j  1,...n
xij  quantità di flusso sull' arco (i, j)
cij  costo di trasporto di un' unità di flusso sull' arco (i, j)
bi  valore associato al nodo i :
se bi  0 : nodo offerta
se bi  0 : nodo domanda
se bi  0 : nodo di passaggio
12
Problema del Flusso a costo Minimo
FORMULAZIONE
In forma matriciale:
T
min c x
Ax  b
x0
NOTA:
1. La matrice A(m,n) è la matrice di incidenza nodo-arco,
ogni colonna è associata ad un arco, il singolo elemento
della matrice è dato da:
a ij  ei  e j
(ei vettore colonna con tutti 0 eccetto un 1 in posizione i-ma.)
2. Il rango di questa matrice è: r(A)=m-1
13