关联矩阵（incidence matrix)是描述和实现图算法的另一重要方式，对于含有n个顶点、e条边的图，

图中顶点数，c是边数。因此，如果边j依附于顶点i，则INC[i][j]=1。图8-16(b)就是图8-16(a)所示图的关联矩阵。注意，在使用关联矩阵时应把图8-16(a)中所有的边从上到下、从左到右顺序编号。

(1)如果ADJ是图G=(V，E)的邻接矩阵，INC是关联矩阵，试说明在什么条件下将有ADJ=lNC×INCT-I，其中，INC是矩阵INC的转置矩阵，I是单位矩阵。两个nxn的矩阵的乘积C=A×B定义为公式中的“∪”定义为按位加，“∩”定义为按位乘。

(2)设用邻接矩阵表示的图的定义如下。

试仿照上述定义，建立用关联矩阵表示的图的结构。

(3)以关联矩阵为存储结构，实现图的DFS的递归算法。

一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有(31)个0元素。

A．n2-2e

B．2e-1

C．n2-e

D．e2

一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有(33)个零元素。

A．e

B．2e

C．n2-e

D．n2-2e

一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有(36)个零元素。

A．e

B．2e

C．n2-e

D．n2-2e

对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为(24)，利用Kruskal算法生成最小生成树的时间复杂度为(25)。

A．O((n+1)2)

B．O(n2)

C．O(n2-1)

D．(n2+1)

A.e

B.2e

C.n2-e

D.n2-2e

具有n(n＞0)个顶点的无向图最多含有(37)条边。

A．n(n-1)

B．

C．

D．n(n+1)

●对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为 (24) ，利用Kruskal算法生成最小生成树的时间复杂度为 (25) 。

(24) A．O((n+1)2 )

B．O(n2 )

C．O(n2-1)

D．(n2+1)

(25) A．O(log2e)

B．O(log2e-1)

C．O(elog2e)

D．以上都不对

具有n(n＞0)个顶点的无向图最多含有(37)条边。

A．n(n-1)

B．n(n+1)

C．n(n-1)

D．n(n+1)