问题 单项选择题

设有一个无向图G=(V,E)和G′=(V′,E′),如果G′为G的生成树,则下面不正确的说法是 (40)

A.G′为G的子图

B.G′为G的极小连通子图且V′=V

C.G′为G的一个无环子图

D.G′为G的边通分量

答案

参考答案:D

解析:[分析]
本题考查无向图与其生成树的关系。
对于无向图而言,如果无向图G是一个连通图,在对其进行遍历时,一次可以遍历所有顶点,得到的极小连通子图是一棵生成树,树中包含了图的所有顶点,但不一定包含所有的边;如果无向图G是一个非连通图,在对其进行遍历时,得到的是森林,这个森林是由图的连通分量的生成树组成的,森林中也不一定包含图中所有的边。因此,G'不一定为G的边通分量。

填空题
单项选择题