Distanza tra due Spanning Tree
Distanza
Siano
e spanning tree di un medesimo grafo connesso . Definiamo la distanza tra
e ponendo:
Segnatura Grafo Pesato
Sia
Segnatura
La Segnatura
è la sequenza dei pesi degli archi di in ordine non decrescente.
Unicità della Segnatura
Teorema
Due qualunque MST di uno stesso grafo pesato non orientato e connesso hanno la medesima segnatura.
Dimostrazione
-
Procediamo per assurdo:
-
Sia
un grafo non orientato connesso e pesato, con e , contenente degli MST con segnature distinte -
In particolare, siano
e due MST di con segnature distinte, e tali che la loro distanza sia minima. -
Sia
un arco di peso minimo in senza perdita di generalità, possiamo supporre che appartenga a , e non a . -
Sia
il taglio di indotto cancellando l’arco dall’MST -
Sia
un cammino in da a , e sia un arco in che attraversa il taglio -
Per la minimalità di
in , si ha -
Pertanto, posto
si ha che: è uno spanning tree di , - e
- da cui
e quindi e è un MST di G
-
Si noti inoltre che:
- Questo perché
- e quindi:
contraddicendo la minimalità di
-
Questa contraddizione deriva dall’aver supposto che possano esistere grafi pesati non orientati e connessi dotati di MST con segnature distinte. Pertanto il teorema risulta dimostrato
-
Cammino
-
-
Visualizzazione distanze con
rimosso: -
Corollario
Un grafo non orientato e connesso con funzione peso iniettiva ha unico MST
Dimostrazione
Sia
Dall’iniettività di
facile eh?
Minimalità della Segnatura
- Siano
due di numeri reali, con lessicograficamente. - Cioè se e solo se:
per qualche . - Esempio:
precede
Proprietà A
La relazione di precedenza lessicografica
Proprietà B
Sia
per qualche
Allora la segnatura di
Teorema Minimalità
Teorema
Uno spanning tree è un MST se e solo se la sua segnatura è lessicograficamente minima
Dimostrazione
Procediamo per assurdo, supponendo che esista un grafo pesato
Siano
Inoltre: sia
Abbiamo due casi:
-
Caso
- Sia
il taglio di G indotto cancellando l’arco dall’MST . - Sia
un cammino in da a e sia un arco in che attraversa il taglio - Pertanto
- Poiché
è uno spanning tree, si ha: - Ma in tal caso avremmo
, che contraddice la minimalità di
- Sia
-
Caso
- Sia
il taglio di G indotto cancellando l’arco dall’MST . - Sia
un cammino in da a e sia un arco in che attraversa il taglio - Caso analogo al prima,
è uno spanning tree di G. - Poiché
, si ha che: - Si ha dunque
- Inoltre, per la stessa relazione sulla distanza, la coppia
contraddice la minimalità di
- Sia
Dimostrazione
Sia
Per la prima parte del teorema, la segnatura di