Fast question about minimum spanning trees
If any edge from a spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ?
Right now, I'm trying to draw on paper some graphs to prove that it doesn't. Please correct me if it does, or help me find an开发者_运维技巧 example if it doesn't.
Thanks in advance.
A triangle with edge weights 2,2,1.
EDIT:
There are three different spanning trees with costs 3 (1+2),3 (2+1) and 4 (2+2) in this graph. all the edges from the spanning tree with cost 4 are contained in one of the minimum spanning trees with cost 3, and it is NOT minimal.
精彩评论