2. 计算机
  3. 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有(15)个顶点。

若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有(15)个顶点。

admin2019-06-12  23
问题 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有(15)个顶点。
选项 A、11
B、10
C、9
D、8
答案B
解析 因为G为非连通图，所以G中至少含有两个连通子图，而且该图不含有回路和多重边。题目问的是至少有多少个顶点，因此一个连通图可看成是只有1个顶点，另一个连通图可看成是一个完全图(因为完全图在最少顶点的情况下能得到的边数最多)，这样，该问题就转化为“36条边的完全图有多少个顶点”，因为具有n个顶点的无向完全图的边的条数为n×(n-1)／2，可以算出n=9满足条件。再加上另一个连通图(只有一个点)，则图G至少有10个顶点。
转载请注明原文地址:https://jikaoti.com/ti/wMf7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)