Domande su Albero minimo di copertura

[eusebi1]

Sia G = (V;E;w) un grafo connesso, pesato e non orientato. Indicare se le seguenti aermazioni sono vere o false, motivando
la risposta.

a. Se T e un albero minimo di copertura (di supporto) di G e T0 e un albero di copertura di G, allora w(T) < w(T0).
sì per definizione

c. Se w e iniettiva, T e un albero minimo di copertura ed e e un arco di T, puo esistere T0 albero minimo di copertura che
non contiene e.

No l'albero è unico (biettiva) se ci fossero archi di peso uguale a quello di e potrebbe essere vero.

Giusto ?

[hamming_burst]

"eusebi":Sia G = (V;E;w) un grafo connesso, pesato e non orientato. Indicare se le seguenti aermazioni sono vere o false, motivando
la risposta.

a. Se T e un albero minimo di copertura (di supporto) di G e T0 e un albero di copertura di G, allora w(T) < w(T0).
sì per definizione

Nì.
più corretto dire $w(T) <= w(T0)$. Un albero di copertura può essere anche minimo

c. Se w e iniettiva, T e un albero minimo di copertura ed e e un arco di T, puo esistere T0 albero minimo di copertura che
non contiene e.

No l'albero è unico (biettiva) se ci fossero archi di peso uguale a quello di e potrebbe essere vero.

Se w() è iniettiva che vuol dire? Da definizione vuol dire che ci son associati più pesi ad un unico arco E qui si può interpretare che sì, in T0 può essere che non contiene E (bisognerebbe sapere come è definita la funzione peso, es. a tempo t0 a peso 10 a tempo t3 a peso 1 ed un algoritmo per il calcolo di MST può produrre due alberi differenti...).
w() valuta un arco non l'albero totale.

In casi di archi con pesi uguali che crano due cammini
-(u,k) (k,t) (t,v)
- (u,d) (d,r) (r,v)

allora può essere che in T ci sia l'arco (d,r), e in T0 (k,t).

[eusebi1]

Ho riportato il testo ell'esercizio ed ho interpretato la biettività rispetto a dominio degli archi e un codominio N dei numeri positivi. Se gli archi fossero eguali potremmo avere più alberi minimi di copertura. In effetti il dubbio era proprio relativo alla correttezza dell'interpretazione del termine iniettiva.

[hamming_burst]

ma il dubbio lo hai risolto?

[eusebi1]

Secondo me aveva semplicemente complicato (reso + elegante) il fatto che tutti gli archi avevamo pesi diversi.