必考题

考点

数据结构-图-最小生成树

面5笔5

p个顶点p条边的连通图中至少有多少个生成树？

A.2

B.3

C.4

D.p

解答

正确答案是 B

p个顶点的连通图图至少p-1条边，p条边必有一环，环至少有3条边组成，所以生成树至少有排列的C3取1等于3个，最多应该是p个(p个顶点组成的大环，随便去条边都是生成树)

咳咳咳

2023-07-11 23:00:00

看了两遍，慢慢消化吸收知识点

0 0

希望找回我家的猪

2023-02-05 21:00:00

写的不错共勉~，最近也在开始写博客。大佬们来翻牌啊！

0 0

埃蒙迷路患者

2022-10-17 21:00:00

云里雾里地听完了……

0 0

鹜落霜洲

2021-09-13 11:10:00

学到数据库了感觉有些难度我太难了

0 0

碧海问舟

2018-10-13 11:58:59

至多p个至少3个

0 0

小可爱

2018-10-13 11:58:52

我大概懂了一点，应该就是，p个顶点的连通图在p-1条边时，图本身就是一棵生成树，然后还有一条多余的边，所以必然会有一个回路的出现，一个回路至少有三条边(题目问的至少)，在生成树时，因为本身是在树的基础之上加了一条边，所以，只需要将这三条边的回路去掉任意一条边，就能生成树。(理解不透彻，逻辑不太清楚)

0 0

站桩灵

2018-10-13 11:58:39

不懂，求解答

0 0

心意

2018-10-13 11:58:33

连通图相当于在树上多加了一条边

所以其中必然会有一个回路

生成树的数量应该等于回路的边数
如果不考虑重边和自环的情况最小的回路必然是3

所以选B

0 0