开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜