试题-图G是n个顶点的无向完全图,则下列说法正确的有:()

题目

图G是n个顶点的无向完全图,则下列说法正确的有:()

A.G的邻接多重表需要n(n-1)个边结点和n个顶点结点

B.G的连通分量个数最少

C.G为连通图

D.G所有顶点的度的总和为n(n-1)

上一题 下一题

解答

正确答案是 B C D

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。

A，边的条数为C（n,2）=n(n-1)/2

B，G是完全图，必定是连通图。所以连通分量只有其自身

C，G是完全图，必定是连通图

D，每个顶点都与其余n-1个顶点相连，则n个顶点度的和为n(n-1)

C 8条回复评论

老瑭

今年开放的岗位好多

发表于 2021-09-14 07:25:00

0 0

努力努力再努力

楼主的这篇文章写得很精彩，总结的很到位，支持一个

发表于 2021-09-13 14:35:00

0 0

改造家

A选项应该是n(n-1)/2条边和n的顶点。

发表于 2018-10-13 14:33:57

0 0

小小精灵

G的邻接多重表需要n(n-1)/2个边结点，A错，BCD都是对的。

发表于 2018-10-13 14:33:49

0 0

子不语

粗心看成了邻接表了。。。

发表于 2018-10-13 14:33:41

0 0

资深90后

任何连通图的联通分量就是他自己！切记，切记

发表于 2018-10-13 14:33:35

0 0

大葫芦

邻接表的话A正确，邻接多重表的话，不会用重复的表，所以是N*(N-1)/2

发表于 2018-10-13 14:33:00

0 0

雨声敲敲

妈蛋。。我选了A

发表于 2018-10-13 14:32:44

0 0

问题信息

分类：数据结构 - 图的属性

难度:

最新校招难题刷题，快来进刷题群吧