T是连通无向图G的生成树的充分必要条件是:T是G的连通生成子图,且T有n-1条边,这里n是G的结点数.

设G=(V，E)是有P个结点，S条边的连通图，则从G中删去多少条边，才能确定图G的一棵生成树．

图7中所示的无向图G中，实线边所表示的子图为G的一棵生成树T。

(1)求G对应T的所有基本回路。

(2)求G对应T的所有基本割集。

设无向图G=(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面说法中错误的是 ()。

A．G’是G的子图

B．G’是G的连通分量

C．G’是G的极小连通子图且V=V’

D．G’是G的一个无环子图

以下叙述中正解的是（）。

A．只要无向连通图中没有权值相同的边，则其最小生成树唯一

B．只要无向图中有权值相同的边，则其最小生成树一定不唯一

C．从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树

D．设连通图G含有n个顶点，则含有n个顶点n-1条边的子图一定是G的生成树

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

A．G′为G的子图

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

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

D．G′为G的边通分量

A、T有n个点n条边

B、T的长度等于G的每条边的长度之和

C、T有n个点n+1条边

D、T有n-1个点n条边

无向图G如图16.26所示，其中实线边为G的一棵生成树T。

(1)求G对应T的基本回路系统。

(2)求G对应T的基本割集系统。

连通图G中有n个顶点，G的生成树是()连通子图。

A.包含G的所有顶点

B.包含G的所有边

C.不包含G的所有顶点

D.包含G的所有顶点和所有边