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

题目

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

A.2

B.3

C.4

D.p

上一题 下一题

解答

正确答案是 B

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

C 8条回复评论

咳咳咳

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

发表于 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

碧海问舟

至多p个至少3个

发表于 2018-10-13 11:58:59

0 0

小可爱

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

发表于 2018-10-13 11:58:52

0 0

站桩灵

不懂，求解答

发表于 2018-10-13 11:58:39

0 0