n个顶点,m条边的全连通图,至少去掉几条边才能构成一棵树?

n个顶点,m条边的全连通图,至少去掉几条边才能构成一棵树?
晕了,google的面试题···
182084958 1年前 已收到1个回答 举报

www198504 幼苗

共回答了20个问题采纳率:95% 举报

n个顶点的树一定有n-1条边(证明可以看任何一本图论书),所以需要去掉m-(n-1)=m-n+1条边

1年前

5
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.028 s. - webmaster@yulucn.com