对具有n个顶点的图其生成树有且仅有________条边。

第1题：

第2题：

如果无向图G有n个顶点，那么G的一棵生成树有且仅有（）条边。

正确答案:n-1

第3题：

连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。

正确答案:错误

第4题：

一棵有N个顶点的生成树有且仅有（）条边。

正确答案:N-1

第5题：

一个连通图的生成树是该图的（）连通子图。若这个连通图有n个顶点，则它的生成树有（）条边。

正确答案:极小（最小）；n-1

第6题：

由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。

• A、 n
• B、 n-1
• C、 n+1
• D、 2×n

正确答案:B

第7题：

对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（）。

正确答案:o（elg0）

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

关于图的生成树，下列说法不正确的是（）。

• A、它又称为图的支撑树。
• B、图有生成树的充要条件是该图为连通图。
• C、图的生成树是唯一的。
• D、顶点数为n的图的生成树有n-1条边。

正确答案:C

第15题：

图的生成树（），n个顶点的生成树有（）条边。

正确答案:唯一性不能确定；n-1

第16题：

具有n个顶点的有向无环图最多有多少条边？

正确答案: 具有n个顶点的有向无环图最多有n×（n—1）/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。

第17题：

如果n个顶点的图是一个环，则它有（）棵生成树。（以任意一顶点为起点，得到n-1条边）

正确答案:n

第18题：

一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。

正确答案:极小连通子图

第19题：

对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。

正确答案:n；n-1

第20题：

第21题：

第22题：

第23题：

第24题：