Il problema del minimo albero
ricoprente
in un grafo con archi privati
Un problema molto noto…
INPUT: G=(V,E): grafo non diretto pesato, w(e) 
R+ per ogni e E
T è un albero ricoprente di G se:


1.
2.
3.

T è un albero
T è un sottografo di G
T contiene tutti i nodi di G
OUTPUT: T=(V,ET) minimo albero ricoprente di G,
ovvero che minimizza il peso totale w(T)= w(e)
e  ET

Miglior algoritmo centralizzato richiede tempo
O(m (m,n))
La funzione di Ackermann
A(i,j) e la sua inversa (m,n)
A(i,j) per piccoli valori di i e j
j=1
j=2
j=3
j=4
i=1
2
22
23
24
i=2
22
22 2
2
22
22 2
2
22
2
..
i=3
22
2
.2 16
.
.
2
2
22
2.
2
.
.
2
.. 16
2
..
22
2
2
2
..
2
2
2
16
La funzione (m,n)
Proprietà
1.
Fissato n, (m,n) è monotonicamente
decrescente al crescere di m
(m,n)= min {i>0 : A(i, m/n) > log2 n}
crescente in m
2.
(n,n)  
per n  
(n,n)= min {i>0 : A(i, n/n) > log2 n}
= min {i>0 : A(i, 1) > log2 n}

Osservazione
(m,n)  4 per ogni scopo pratico (cioè
per valori di n ragionevoli)
(m,n)= min {i>0 : A(i, m/n) > log2 n}
A(4,m/n)  A(4,1) = A(3,2)
.2 16
.
.
=22
>> 1080
 numero stimato di atomi
nell’universo osservabile
 quindi (m,n)  4 per ogni n<210
80
Il problema del MSTegoistico


Input: un grafo G=(V,E) biconnesso sugli
archi, in cui ogni arco corrisponde in modo
biunivoco ad un insieme di agenti egoisti; il
tipo di un agente è il costo di utilizzo
dell’arco (quindi tipo > 0); la sua valutazione
è uguale al suo tipo;
SCF: un vero MST di G=(V,E,t).
Meccanismo VCG

Il problema è utilitario  VCG-mechanism M= <g(r), p(x)>:


g(r): dato il grafo G e le dichiarazioni r=(r1,…,rm), calcola il MST
T=(V,ET) di G=(V,E,r)
pe: Per ogni arco e  E, pe =j≠e vj(rj,x(r-e)) -j≠e vj(rj,x) cioè
pe=w(TG-e)-w(T)+ re
pe=0

se eET,
altrimenti.
Per ogni e T dobbiamo calcolare TG-e, ovvero il MST di
rimpiazzo per e (MST in G-e =(V,E\{e},r-e))
Ipotesi di lavoro: Grafo 2-edge connesso (altrimenti TG-e
potrebbe non esistere  il possessore dell’arco e “terrebbe
in pugno” il sistema!)
Una soluzione banale
e T applichiamo l’algoritmo di calcolo
dell’MST al grafo G-e
Complessità: n-1 archi dell’MST per
O(m (m,n)): O(nm (m,n))
La soluzione efficiente che proponiamo
costerà ancora O(m (m,n))!!!
Un problema correlato: l’analisi di
sensitività degli archi di un MST

Input



grafo G=(V,E) pesato non orientato
T=(V,ET) minimo albero ricoprente di G
Domanda

quanto possono aumentare i pesi w(e) (e  T)
prima di inficiare la minimalità di T?
Esempio
4
11
10
13
6
8
8
10
2
1
3
7
9
Notazioni
G=(V,E), T albero ricoprente di G. Definiamo:
 Per ogni f=(x,y)  E\E(T)


T(f): (unico) cammino semplice in T che unisce x
ey
Per ogni e  E(T)

C(e)={f  E\E(T): e  T(f)}
Proprietà dei cicli
Teorema: Sia G=(V,E) un grafo non orientato
e pesato, sia e l’arco più pesante di un
qualsiasi ciclo in G. Allora e  MST(G)
Dim (per assurdo): Sia e l’arco più pesante
in un ciclo C={e }P, e supponiamo e  T
X
P
e
V\X
T’=T \ {e}  {e’}
w(e’) < w(e)  w(T’) < w(T)
e’  T
T non è MST(G)
Condizione di minimalità di un MST
Corollario
 G=(V,E) grafo non diretto, connesso,
pesato
 T albero ricoprente di G.
allora
 T è minimo se e soltanto se per ogni arco
f non dell’albero vale:
w(f)  w(e)
per ogni e in T(f)
…quindi…


Se e è un arco dell’MST, esso rimane
minimo finché w(e) non cresce oltre w(f),
dove f è l’arco più leggero che forma un
ciclo con e (f è chiamato arco di swap per
e); chiamiamo tale valore up(e)
Più formalmente, per ogni e  E(T)


up(e)= minf  C(e) w(f)
swap(e)= arg minf  C(e) w(f)
Analisi di sensitività degli archi
del MST
C(e)
4
11
10
13
6
e
8
10
up(e)=8
2
1
3
7
9
Osservazione
Calcolare tutti i valori up(e) è
equivalente a calcolare il peso di un MST
di G-e per ogni e di T; infatti
w(TG-e)=w(T)-w(e)+up(e)
 Nel meccanismo VCG il pagamento pe di
un arco e della soluzione è esattamente
pari ad up(e)!!

Idea dell’algoritmo efficiente
Per ogni e  E(T) guardare efficientemente
tutti gli archi che formano un ciclo con e e
prendere il minimo (up(e))
Il Transmuter
Dato G=(V,E) e un suo albero ricoprente T, un
transmuter è un grafo diretto aciclico D che
rappresenta in modo compatto l’insieme dei cicli
fondamentali di G rispetto a T, ovvero l’insieme {T(f) :
f arco non dell’albero}
D conterrà:


1.
2.
3.

Una sorgente (nodo con grado entrante nullo) s(e) per ogni
arco e di T
Un pozzo (nodo con grado uscente nullo) t(f) per ogni arco f
non in T
Un certo numero di nodi ausiliari con grado entrante pari a 2 e
grado uscente diverso da zero.
Proprietà fondamentale: c’è un cammino in D da una
data sorgente s(e) a un pozzo t(f) se e solo se e  T(f)
Un esempio
Come si costruisce un transmuter



Tarjan ha mostrato che ad ogni albero ricoprente
di un grafo può essere associato un transmuter
con O(m (m,n)) nodi ed archi, il quale può essere
calcolato in tempo O(m (m,n))
La costruzione è un’estensione delle tecniche
usate per mantenere efficientemente insiemi di
foreste disgiunte sottoposte a operazioni di
LINK e operazioni di EVAL
R. E. Tarjan, Application of path compression on
balanced trees, J. ACM 26 (1979) pp 690-715
Ordinamento topologico



D=(N,A) grafo diretto. Un ordinamento
topologico di D è un ordinamento v1, v2, …,vn dei
nodi tale che per ogni arco (vi, vj) A, vale i < j.
D ammette un ordinamento topologico se e solo
se D è un DAG (grafo diretto aciclico).
Un ordinamento topologico dei nodi può essere
trovato (se esiste) in tempo O(n+m).
Calcolo degli incrementi per
gli archi dell’albero


Ordiniamo topologicamente il transmuter (che è un
DAG)
Etichettiamo ogni nodo del transmuter con un
valore reale processando i nodi in ordine topologico
inverso:



Etichettiamo ogni pozzo t(f) con il valore w(f) (associamo
al valore anche l’arco f )
Etichettiamo ogni nodo v che non è un pozzo con il valore
minimo fra i valori dei suoi (immediati) successori
Quando tutti i nodi sono etichettati ogni sorgente
s(e) è etichettata con il valore up(e) (e relativo
arco di swap)
Calcolo dei valori up(e)
7
2
8
5
6
9
7
4
7
7
7
8
11
6
9
10
6
6
6
9
3
10
9
10
6
10
11
Complessità temporale
1.
2.
Costruzione Transmuter: O(m (m,n))
Calcolo valori up(e):
Trovare l’ordinamento topologico: O(m (m,n))
Processare il transmuter: O(m (m,n))
Complessità computazionale del VCG
Teorema
Il meccanismo VCG per il problema del MST può
essere implementato in tempo O(m (m,n)).
Dim
Complessità di g(٠): O(m (m,n))
Complessità di p(٠): calcolo tutti i valori up(e) in
tempo O(m (m,n)).