一道数据结构的填空题题,
题目
一道数据结构的填空题题,
若非连通无向图G含有21条边,则G的顶点个数至少为多少?
PS:但没思路.
别单纯只给答案,思路,这种题应该怎么想给详细说下!或者有什么公式,套公式即可,请把公式列出.
答案
如果一个图允许有多重边,则21个自环就可以解决问题,所以连通图只需要一个顶点,非连通图2个顶点.
当然一般是说不允许两个顶点间有多条边的,则非连通图至少分成两个连通子图,每一子图若干顶点.任何一个连通部分若有n个顶点,则最多有n*(n-1)/2条边,可以通过不太复杂的分析得到,平分边或者多于两个子图会增加顶点数,这样结论就是:
8个顶点,7个顶点之间点点连接,外加一个孤立顶点.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 100个和尚100个馒头,大和尚一人得3个,小和尚3人分1个,问大小和尚各有多少?
- 六年的小学生活,我们感受过成功的喜悦,也体验过失败的酸楚,以“酸甜苦辣”中任选种感受,写校园生活.
- 作文 以瞬间为话题
- 用50g碳酸钙与足量盐酸反映,能制取多少mol二氧化碳
- I bought a watch. It was made in Japan.合成一个句子 I bought a watch _______ _____Japan. 两个空
- 先化简再求值:(a+2b)(3a-b)-(2a+b)(a+6b),其中(a-3)平方+|b-2|=0
- 在钝角ABC中,角A,B,C所对的边分别为a,b,c,已知a,b,c成等比数列,且sinAsinC=3/4,求角B的大小
- YangLiwei_____around the Earth on October 15,2003and _____the first Chinese astronaut in space.
- 五年级数学(分数除法、还有额外分数)
- 一幅地图上有一块面积为1平方厘米的图形,正好表示地面上1平方千米的一块农田,那么这幅地图的比例尺是1:100000._.