Costruzione MST distribuita in O (registro n) round in una cricca

Question

Sto leggendo il giornale Costruzione MST in O (log log n) Round di comunicazione in una cricca e cercando di capire l'analisi della correttezza, in pagina 5.

Mostra per induzione su K (numero di fase) che l'albero di spanning, per ogni cluster F (dalla fase K), è effettivamente un frammento MST di quel cluster di vertici.

L'affermazione è ovviamente banale per il caso di base, poiché i cluster sono singoli di vertici. Per mostrare la fase di induzione, è sufficiente mostrare che ogni bordo $ e $ (dove $ X left (e a destra) = left (f_ {1}, f_ {2} a destra), f_ {1} in hat {f_ {1}}, f_ {2} in in in in in in in in in in in in in hat {f_ {2}} $, dove $ F_ {1}, f_ {2} $ sono i cluster originali, cioè i componenti collegati del round precedente, ora contratti in un vertice e $ hat {f_ {1}}, hat {f_ {2}} $ sono i loro super cluster, cioè i componenti collegati li contengono, creati come parte di questa procedura in fase $ k $) scelto dalla procedura const_frags è effettivamente un bordo in uscita (MWOE) di entrambi $ H_ {1} = underset {f in hat {f_ {1}}} { bigcup} f $ o $ H_ {2} = underset {f in hat {f_ {2}}} { bigcup} f $. Presumono che questo $ e $ è stato scelto come parte di $ F_1 $'S $ mu $ bordi di peso in uscita più leggeri e voglio dimostrarlo $ e $ è davvero il mwoe di $ H_1 $. Quindi assumono diversamente, che esista $ e '$ di peso inferiore a $ e $ che è in uscita da $ H_1 $.

Quello che non capisco è, perché lo assumono $ e '$ è di cluster $ F_1 $ anche? L'unica cosa che sappiamo $ e '$ è che è in uscita da $ H_1 $. Questo significa che questo Potere essere estroverso da un altro cluster $ F ' in hat {f_ {1}} backslash left {f_ {1} a destra } $. Gradirei qualsiasi aiuto! Grazie!