应用题:已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。

第1题：

6、下列哪些说法正确

A．连通图G的生成树T是G的子图，且T的顶点集等于G的顶点集。

B．连通图G有n个顶点，则G的生成树的边数为n-1.

C．在树T中任意去掉一条边e后，得到的图T-e不连通。

D．连通图T的生成树唯一。

第2题：

1、如果从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A．强连通图

B．连通图

C．有回路

D．一棵树

第3题：

3、对于n个顶点的连通图G来说，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。（）

第4题：

已知一个图的顶点集V各边集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 图 深度优先序列 广度优先序列 邻接矩阵表示时 邻接表表示时

第5题：

一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（）