图的生成树是指（）A．无向图中包含所有顶点的极小连通子图B．无向图中包含所有顶点的极大连通子图C．无向图中的连通分量D．无向图中的极大连通子图

第1题：

第2题：

以下说法不正确的是（）。

A连通图G一定存在生成树

B连通图G的生成树中一定包含G的所有顶点

C连通图G的生成树中不一定包含G的所有边

D连通图G的生成树可以是不连通的

D
略

第3题：

什么是图的生成树？生成树主要有哪两种求法？简述二者的求解思路。

正确答案: （1）设G是一个连通图，T是G的一个子图且是一棵树，若T包含G的所有节点，则称T是G的一棵生成树，也称支撑树。由定义可知，只有连通图才有生成树；反之，有生成树的图必为连通图。
（2）求取生成树的两种常用的方法：
破圈法：拆除图中的所有回路并使其保持连通，就能得到G的～棵生成树。
避圈法：在有n个点的连通图G中任选一条边（及其节点）；选取第2，3，„条边，使之不与已选的边形成回路；直到选取完n-1条边且不出现回路结束。

第4题：

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

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

正确答案:C

第5题：

带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

正确答案:正确

第6题：

最小生成树指的是（）。

• A、由连通网所得到的边数最少的生成树
• B、由连通网所得到的顶点数相对较少的生成树
• C、连通网中所有生成树中权值之和为最小的生成树
• D、连通网的极小连通子图

正确答案:C

第7题：

一个无向连通图的生成树是图的极小的连通子图。

正确答案:正确

第8题：

一棵无向连通图的生成树是其极大的连通子图

正确答案:错误

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

图的生成树是惟一的。

正确答案:错误

第15题：

从连通图中生成树，以下叙述（）正确。

• A、任一连通图必有支撑树
• B、任一连通图生成的支撑树必唯一
• C、在支撑树中再增加一条边后必含圈
• D、任一连通图生成的各个支撑树其边数必相同

正确答案:A,C,D

第16题：

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

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

第17题：

图G的生成树是该图的一个极小连通子图

正确答案:错误

第18题：

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

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

第19题：

以下有关联通图的说法不正确的是（）。

• A、连通图G一定存在生成树
• B、连通图G的生成树中一定包含G的所有顶点
• C、连通图G的生成制中不一定包含G的所有边
• D、连通图G的生成树可以是不连同的

正确答案:D

第20题：

第21题：

第22题：

第23题：

第24题：