Testo completo
ESERCIZIO DI ASD DEL 11 MAGGIO 2009
Minimum Spanning Tree
Siano T1 e T2 due minimum spanning tree di un grafo G = (N, E, W ) e siano L1
ed L2 le liste ordinate dei pesi degli archi di T1 e T2rispettivamente.
1 Dimostrare che L1= L2.
2 Dimostrare o refutare la seguente affermazione. Se A ⊆ E `e tale che la lista ordinata dei pesi di A `e uguale ad L1, allora A `e un minimum spanning tree di G.
Date: 11 Maggio 2009.
1
Documenti correlati
Suggerimento: Scrivere e risolvere l’equazione ricorsiva di complessit` a nel caso peggiore in funzione dell’altezza. Date: 16
Si consideri il problema di costruire un B-tree T di grado t che contenga tutte le chiavi di T 1 , tutte le chiavi di T 2 e la chiave k.. 1 Si scriva lo pseudocodice di una
Suggerimento: Procedere come nel caso di unione di due RB-tree vista a lezione, facendo attenzione ai nodi pieni.. 2 Si dimostri la correttezza della
Tutte le altre istruzioni richiedono un numero di op- erazioni limitato superiormente dall’altezza dei
Si consideri un’estensione della struttura dati “Disjoint-Sets” in cui oltre alle oper- azioni Make, Union, Find, vengono introdotte le operazioni:..
Si consideri un’estensione della struttura dati “Disjoint-Sets” in cui oltre alle oper- azioni Make, Union, Find, vengono introdotte le operazioni:..
Sia G = (V, E) un grafo non orientato,
Suggerimento: La procedura pi` u efficiente che si pu` o ottenere opera nello stesso tempo di una visita BFS. 3 Se ne dimostri
