• Non ci sono risultati.

ESERCIZIO DI ASD DEL 11 MAGGIO 2009 Minimum Spanning Tree Siano T

N/A
N/A
Protected

Academic year: 2021

Condividi "ESERCIZIO DI ASD DEL 11 MAGGIO 2009 Minimum Spanning Tree Siano T"

Copied!
1
0
0

Testo completo

(1)

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.

Suggerimento: Si proceda per assurdo e si ragioni sul minimo indice su cui le due liste differiscono.

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.

Suggerimento: Per dimostrare che l’affermazione `e corretta occorre ver- ificare che A soddisfa tutte le condizioni presenti nella definizione di min- imum spanning tree. Per refutare l’affermazione occorre invece trovare un controesempio.

Date: 11 Maggio 2009.

1

Riferimenti

Documenti correlati

*Sono invitati ad intervenire: Capi Gruppo Camera dei Deputati e Senato della Repubblica, Presidente e componenti Commissione Igiene e Sanità del Senato della

vista la relazione dell’Ufficio Trattamento Economico in data 4 maggio 2021, che fa parte integrante della presente determina, relativa alla partecipazione dei dipendenti

Quindi tutti i minimum spanning tree di G avranno lista dei pesi uguale

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione delle lettere dell’alfabeto (quindi un modo di disporre ordinatamente le 21

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione delle lettere dell’alfabeto (quindi un modo di disporre ordinatamente le 21

Egli scrive: «La Chiesa dell’epoca di Galileo si attenne alla ragione più che lo stesso Galileo, e prese in considerazione anche le conseguenze etiche e sociali della

– Ad ogni passo viene aggiunto l'arco di peso minimo che collega un nodo già raggiunto dell'albero con uno non ancora raggiunto. Prim: Shortest connection networks and

[r]