在一个图中，若一条边的两个端点相同，则称该边为________。

若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。如图3-9所示，试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件，并编写基于此结构的相应的插入(EnQueue)新元素和删除(DlQueue)算法。

在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算时间较少，

A、Prim

B、Kruskal

若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。

(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将把图分割成两个连通分量。

(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法，判断连通图G中是否有桥，若有。输出这样的桥。

表示图的另一种方法是使用关联矩阵INC[n][e].其中，一行对应于一个顶点，一列对应于一条边，n是图中顶点数，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的递归算法。

在有向图中的一个欧拉画路(Eulercircuit)是这样的一个环：其上的每一条边被访问一次且仅被访问一次。

(l)试证明一个有向图存在欧拉回路的充要条件是该图必须是强连通的且每一个顶点有相同的人度与出度;

(2)设图中的顶点数为n，试描述有向图的数据结构并编写一个时间复杂性为O(n)的算法，在有向图中查找一条欧拉回路(如果它存在).

A.完全图

B.有向完全图

C.无向图

D.简单图