图G=＜V，E＞是简单有向图，邻接矩阵刻画下列哪种关系( )．

假定图G=(V，E)是有向图，V={1，2，…，N}，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到j有边，则A[i，j]=1，否则A[i，j]=0，请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n×n)。

．n]，且压缩存储在B[1．．k]，则k的值至少为()。

A．n(n+1)／2

B．n2／2

C．(n—1)(n+1)／2 D。n(n—1)／2

后写出对G进行宽度优先搜索的算法。

从邻接矩阵可以看出，该图共有（)个顶点。如果是有向图，该图共有（)条有向边;如果是无向图，则共有（

从邻接矩阵可以看出，该图共有()个顶点。如果是有向图，该图共有()条有向边;如果是无向图，则共有()条边。

A、9

B、3

C、6

D、1

E、5

F、4

G、2

H、0

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.

对于下面两个图，分别求：

(1)每个顶点的度，有向图还要求入度和出度。

(2)给出一条从V₀到V₃的简单路径。

(3)给出图的邻接矩阵。

(4)给出图的邻接表。

图中顶点数，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的递归算法。

于此存储结构从顶点A开始进行深度优先搜紫，得到的项点序列是()。

A、ABCDGIFE

B、ABCDGFHE

C、ABGHFECD

D、ABFHEGDC

E、ABEHFGDC

F、ABEHGFCD

若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为（)。

A.G'为G的子图

B.G'为G的连通分量

C.G'为G的极小连通子图且V'=V

D.G'是G的无环子图