n个顶点n条边的无向图（简单图）一定是连通的有环的

2024-12-01 03:11:52

推荐回答（3个）

回答（1）：

一个有n个顶点和n条边的无向图一定是（）。
A．连通的
B．不连通的
C．无环的
D．有环的
正确答案：D
如果一个无向图有n个顶点和n—1条边，可以使它连通但没有环(即生成树)，但再加一条边，在不考虑重边的情形下，就必然会构成环。

回答（2）：

简单图中
A. n个顶点一定连通的条件是边数|E|大于C(n-1,2)，即n-1个顶点构成完全图，再和第n个顶点连接任意一条边可保证连通。
B. n个顶点n-1条边即可构成图的一棵生成树，即最小连通分量，是一个包含图中全部顶点且边数最少（n-1条）的连通图。
C.满足n个顶点n条边的最小n为3，3个顶点3条边即可构成一个环，以此类推n个顶点n条边必定构成环。
D. 正确。

回答（3）：

连通是两个顶点之间有路径即连通，n-1条就够了

n个顶点n条边 的无向图（简单图）一定是 连通的 有环的

n个顶点n条边的无向图（简单图）一定是连通的有环的