MST-Reduce

MST in Grafi Sparsi

Contrazione

Definizione

Una contrazione id un grafo non orientato è un grafo tale che:

• è una partizione di ;
• Ciascuno dei sottografi di G indotti dagli insiemi di vertici è connesso,
• Per ogni coppia con si ha:

MST-Reduce

Dato un grafo non orientato e connesso con funzione peso , descriveremo la procedura MST-Reduce, che costruisce:

• Un Grafo Contratto con funzione peso , con partizione di V tale che
• Una funzione tale che:
• Un insieme di archi tale che:

Tali che: 

Per ogni MST di è un MST di .

Cioè, per ciascun , il sottografo di indotto da è un MST.

MST-Reduce: Implementazione

 

foreach (v in V[G]) do:
	mark[v] = FALSE;
	MAKE-SET(v);
foreach (u in V[G]) do:
	if (mark[u] == FALSE) then:
		 scegli v in Adj[u] tale che w[u,v] è minimizzato
		 UNION(u,v);
		T = T Unito-a {orig[u,v]};
		mark[u] = mark[v] = TRUE;
V[G'] = {FIND-SET(v): v in V[G]};
E[G'] = EMPTY_SET;
foreach (x,y) in E[G] do:
	u = FIND_SET(x);
	v = FIND_SET(y);  
	if (u != v) then:
		if ((u,v) !in E[G']) then: 
			E[G'] = E[G'] Unito-a {(u,v)};
			orig'[u,v] = orig[x,y];
			w'[u,v] = w[x,y];
		else if (w[x,y]<w'[u,v]) then:
			orig'[u,v] = orig[x,y];
			w'[u,v] = w[x,y];
construct lista adiacenza Adj per G' 
return (G', orig', w', T)

Complessità

wip