6
第三部分 图
1.若有5个结点的有向图是强连通图，则最少有( )条弧. 2.有向图中所有顶点的出度之和为n，则入度之和为( ) 3.在任何一个图G中，所有顶点的度数之和等于所有边数之和的( )倍。 4.在有8条边的无向图中，所有顶点的度之和为( ) 5.G是一个非连通无向图，共有9个顶点，则该图最多有( )条边。
6.若无向图的顶点集为{A，B，C，D，E，F，G}，边集为{(A，B)，(A，C)，(B，D)，(E，F)}，则该图含有( )个连通分量。
7.连通有7个顶点的有向图的所有顶点至少需要( )条弧，连通有7个顶点的无向图的所有顶点至少需要( )条边。
8.已知图的顶点集为 {v0,v1,v2,v3,v4} , 其邻接矩阵如下图（左）所示，从顶点v0出发，按照深度优先搜索算法得到的遍历序列为( )，按照广度优先搜索算法得到的遍历序列为( )。
9.已知一个有向图的邻接表如上图（右）所示，顶点V1的入度为( )，顶点V2的出度为( )，从顶点V0出发得到的深度优先遍历序列是( )，从顶点V1出发得到的广度优先遍历序列是( )。
10.已知无向网如下图（左）所示，请使用普里姆(prim)算法，按步骤画出从顶点A开始，构造最小生成树的详细过程。
D972B8152F36A3
11.已知有向网如上图（中）所示， （1）请写出下图的所有拓扑序列。
（2）请求出各顶点事件的最早发生时间Ve和最迟发生时间Vl。 （3）请求出源点A到汇点F的关键路径。
EC12.已知一个有向网G如上图（右）所示，求源点A到其它各顶点的最短路径及长度（写详细求解过程）。 10~12解答：