Imposing edges in Minimum Spanning Tree
share
We are interested in the consequences of imposing edges in T a minimum spanning tree. We prove that the sum of the replacement costs in T of the imposed edges is a lower bounds of the additional costs. More precisely if r-cost(T,e) is the replacement cost of the edge e, we prove that if we impose a set I of nontree edges of T then ∑_e ∈ I r-cost(T,e) ≤ cost(T_e ∈ I), where I is the set of imposed edges and T_e ∈ I a minimum spanning tree containing all the edges of I.
READ FULL TEXT