开发者

Fast question about minimum spanning trees

开发者 https://www.devze.com 2023-01-27 01:28 出处:网络
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 ?

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

精彩评论

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