图[图]去掉任何一个顶点及其与之关联的边之后是哈密顿...

A、完全二部图是哈密顿图

B、强连通的有向图都是哈密顿图

C、哈密顿图去掉一条边后可能仍是哈密顿图

D、设G为n阶无向简单哈密顿图，则对于任意两个不相邻顶点u,v,均有

A、完全二部图是哈密顿图

B、强连通的有向图都是哈密顿图

C、哈密顿图去掉一条边后可能仍是哈密顿图

D、设G为n阶无向简单哈密顿图，则对于任意两个不相邻顶点u,v,均有

关联矩阵(incidence matrix)是描述和实现图算法的另一重要方式，对于含有n个顶点、e条边的图，对应的关联矩阵I[][]共有n行e列。在无向图中，对于任意的0≤i<n和0≤j<e，若第i个顶点与第j条边彼此关联，则定义I[[i][j]=1;否则，定义I[[i][j]=0。

a)关联矩阵与邻接矩阵有何联系?

b)有向图的关联矩阵应如何定义?

c)有向图的关联矩阵，与邻接矩阵又有何联系?

d)基于关联矩阵，可以解决哪些问题?试举一例。

设G是一个用邻接表表示的连通无向图。对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后，G变成由两个或两个以上非空连通分量所组成的图，则称v是原来图G的一个关节顶点。如下图中，只有顶点4和顶点6是关节顶点，而其他顶点都不是关节顶点。试叙述寻找图G的所有关节顶点的算法，并用算法语言(Pascal或C)编写一个实现你所给出的算法的程序。【复旦大学1996八(20分)】

用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

A、

B、

C、

D、

图的生成子图应包含 个顶点，至少 条边

A、

B、

C、

D、

用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：

A、

B、

C、

D、

给定一个有n个顶点的有向图，如果其边的个数达到，则该图一定是完全图。

给定一个有n个顶点的有向图，如果其边的个数达到，则该图一定是连通图。