Il problema del minimo albero ricoprente in un grafo con archi privati.
Il problema del minimo albero ricoprente in un grafo non cooperativo.
-
Upload
guerino-mancini -
Category
Documents
-
view
215 -
download
0
Transcript of Il problema del minimo albero ricoprente in un grafo non cooperativo.
Il problema del minimo albero ricoprente
in un grafo non cooperativo
Un problema molto conosciuto
G=(V,E): grafo non diretto pesato, w(e) R+ per ogni e E (tipo privato dell’agente che possiede l’arco e)
T è un albero ricoprente di G se:1. T è un albero2. T è un sottografo di G3. T tocca tutti i nodi di G
Un problema molto conosciuto
Input: grafo G=(V,E) pesato non orientato
Output: T=(V,ET) albero ricoprente di G che minimizza il
peso totale w(T)= w(e)
Miglior algoritmo centralizzato richiede tempo O(m (m,n))
e ET
La funzione di Ackermann (e la sua inversa)
A(i,j) per piccoli valori di i e j
2 23 24
22
22
222222
222222
22222
216
22
22
2
216
22
22
2
222
2 16
... ..
... ..
..
..
j=1 j=2 j=3 j=4
i=1
i=2
i=3
La funzione (m,n)
Proprietà
1. fissato n, (m,n) monotonicamente decrescente al crescere di m
2. (n,n) per n 3. (m,n) 4 per ogni scopo pratico
(m,n)= min {i>0 : A(i, m/n) > log2 n}
1.
crescente in m
Proprietà
2. (n,n) per n
(n,n)= min {i>0 : A(i, n/n) > log2 n} = min {i>0 : A(i, 1) > log2 n}
Proprietà3. (m,n) 4 per ogni scopo pratico
A(4,m/n) A(4,1) = A(3,2)
=22
2 16.. .
>> 1080
numero stimato di atomi nell’universo osservabile
(m,n)= min {i>0 : A(i, m/n) > log2 n}
Meccanismo VCG per il problema del MST
M= <g(r), p(g(r))> g(r): dato il grafo G e le dichiarazioni r=(r1,…,rm), calcola
il MST di G, T=(V,ET) pe: Per ogni arco e ET pe=w(TG-e)-w(T)+ w(e) (w(e): peso riportato per e)
Per ogni e T dobbiamo calcolare TG-e, ovvero il MST di rimpiazzo per e (MST in G-e =(V,E\{e}))
Ipotesi di lavoro: Grafo 2-edge connesso (altrimenti TG-e potrebbe non esistere il possessore dell’arco e “tiene 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))!!!
Una soluzione un po’ meno banale Proprietà dei tagli di un MST: sia (V’,V’’)
un taglio in G: allora, l’arco di peso minimo che “attraversa” il taglio appartiene all’MST
TG-e coincide con T-e+f, dove f è l’arco di peso minimo che attraversa il taglio indotto dalla rimozione di e da T
Controlliamo gli O(m) archi del taglio suddetto e troviamo f
Complessità: n-1 archi dell’MST per O(m): O(m (m,n)+mn)=O(mn)
L’analisi di sensitività degli archi dell’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
86
2
7
1
9
3
10
4
10
8
13
11
Notazioni
G=(V,E) T albero ricoprente di GDefiniamo Per ogni f=(x,y) E\E(T)
T(f): (unico) cammino in T che unisce x e y Per ogni e E(T)
C(e)={f E\E(T): e T(f)}
Proprietà dei cicli
G=(V,E) grafo non orientato e pesato, e l’arco più pesante in un qualsiasi
ciclo Allora e MST(G)
Dim (per assurdo)Sia e l’arco più pesante in un ciclo
C={e }P, e supponiamo e T
e e’ T
T’=T \ {e} {e’}
w(e’) < w(e) w(T’) < w(T)
T non è MST(G)
X
V\X
P
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 dell’MST
up(e)=86
2
7
1
9
3
10
4
10
8
13
11
e
C(e)
Osservazioni
Calcolare tutti i valori up(e) (swap(e)) vuol dire ricalcolare MST(G-e) per ogni e di T MST(G-e)=MST(G) \{e} {swap(e)}
Nel meccanismo VCG il pagamento pe di un arco e della soluzione è esattamente 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 l’insieme dei cicli fondamentali di G rispetto a T, ovvero l’insieme {T(f) : f arco non dell’albero}
D contiene:1. Una sorgente (nodo con grado entrante nullo) s(e)
per ogni arco e di T2. Un pozzo (nodo con grado uscente nullo) t(f) per
ogni arco f non in T3. Un numero arbitrario di nodi ausiliari 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)
Come si costruisce il transmuter
Tarjan ha mostrato come costruire un transmuter che ha O(m (m,n)) nodi 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
Alcuni richiami di base
D=(N, A) grafo diretto ( |N|=h ) Un ordinamento topologico è un
ordinamento dei nodi di D v1, v2, …,vh
tale che:per ogni arco (vi, vj) A, vale i < j
Alcuni richiami di base
D=(N, A) grafo diretto 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| + |A|) (visita in profondità)
Calcolo degli incrementi per gli archi dell’albero
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)
2
5
3
6
4
9
7
8
96
11
10
7 7 6 6 9 10
7 6 10
7 8 9 6 10 11
Calcolo dei valori up(e)
Complessità
Tempo1. Costruzione Transmuter: O(m (m,n))2. Calcolo valori up(e):
Trovare ordinamento topologico O(m (m,n))Processare il transmuter in O(m (m,n))
Spazio1. O(m (m,n))