若非连通无向图G含有21条边,则G的顶点个数至少为 _______ .

品味qq2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

共1条回复

傲霜凌雪2 共回答了18个问题 | 采纳率100%: 既然是非连通图,则至少有2个子图,每个子图的顶点数至少1个
7个顶点的无向完全图可以包含21条边,因此G的顶点数至少7 + 1 = 8个; 1年前

相关推荐

对于一个非连通无向图,共有28条边,则该图至少有多少个顶点? 对于一个非连通无向图,共有28条边,则该图至少有多少个顶点? 答案是不是9个》 亲亲草语1年前1: jiania 共回答了19个问题 | 采纳率89.5%

就是9个
这个可以构造性的方法来说明
构造:
这样的图至少有9个顶点
证明:
假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图
连通无向图构成条件:边=顶点数*(顶点数-1)/2
顶点数>=1,所以该函数存在单调递增的单值反函数
所以边与顶点为增函数关系
所以28个条边的连通无向图顶点数最少为8个
所以28条边的非连通无向图为9个(加入一个孤立点)

1年前查看全部

一道数据结构的填空题题,若非连通无向图G含有21条边,则G的顶点个数至少为多少?PS：但没思路.别单纯只给答案,思路,这 一道数据结构的填空题题, 若非连通无向图G含有21条边,则G的顶点个数至少为多少? PS：但没思路. 别单纯只给答案,思路,这种题应该怎么想给详细说下!或者有什么公式,套公式即可,请把公式列出. kingson251年前1: lucky6699 共回答了23个问题 | 采纳率91.3%

如果一个图允许有多重边,则21个自环就可以解决问题,所以连通图只需要一个顶点,非连通图2个顶点.
当然一般是说不允许两个顶点间有多条边的,则非连通图至少分成两个连通子图,每一子图若干顶点.任何一个连通部分若有n个顶点,则最多有n*(n-1)/2条边,可以通过不太复杂的分析得到,平分边或者多于两个子图会增加顶点数,这样结论就是：
8个顶点,7个顶点之间点点连接,外加一个孤立顶点.

1年前查看全部

设连通无向图G采用邻接表表示.写出求最小生成树Prim算法的实现代码. 设连通无向图G采用邻接表表示.写出求最小生成树Prim算法的实现代码. 来个具体的例子看看,坐等,来人啊. maoshaxu1年前1: 沸了共回答了22个问题 | 采纳率86.4%

百度一下很多的

1年前查看全部

连通无向图G有k个奇顶点,如果把G变成无奇顶点的图,则在G中至少需要加___ ___条边 连通无向图G有k个奇顶点,如果把G变成无奇顶点的图,则在G中至少需要加___ ___条边 如题,分必给,谢谢 justforenjoy1年前1: 0198177 共回答了14个问题 | 采纳率100%

无向连通图奇点的个数k一定为偶数,因此要想把G变成无奇点的图,至少需要加k/2条边.

1年前查看全部

大家在问