早教吧 育儿知识 作业答案 考试题库 百科 知识分享
早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->

若G是一个具有36条边的非连通无向图(不含自回路和多重边),则图G至少有(64)个顶点。A.11B.10C.9D.8

题目

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

A.11

B.10

C.9

D.8

参考答案
正确答案:B
解析:根据无向图的定义,有n个顶点的无向图至多有n(n-1)/2条边。试题告诉我们,共有36条边,则n(n-1)/2=36解这个方程可得n=9。但这样求得的9个顶点是连通的,而试题要求是非连通图,所以,再增加一个孤立点,因此至少有10个顶点。