计算机科学与技术学院 计算机科学与技术专业 3010216001 张三 一班第七章 图2一、应用题1证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。2请回答下列关于图(Graph)的一些问题：（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边? （2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？3有向图的邻接表存储如下：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。4某田径赛中各选手的参赛项目如右表:姓名参赛项ZHAOABEQIANCDSHUNCEFLIDFAZHOUBF设项目A ,B ,，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件)。（1）根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构;（2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。5下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。6用最短路径算法，求如下图中a到z的最短通路。65ced4bfghijza22496142231234598297（1）对于有向无环图，叙述求拓扑有序序列的步骤；（2）对于以下的图，写出它的四个不同的拓扑有序序列。217436588下表给出了某工程各工序之间的优先关系和各工序所需时间（1）画出相应的AOE网。（2）列出各事件的最早发生时间，最迟发生时间。（3）找出关键路径并指明完成该工程所需最短时间。工序代号ABCDEFGHIJKLMN所需时间15105081540300151206015302040先驱工作-A,BBC,DBEG,IEIF,IH,J,KLG二、算法设计题1设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1n或0n-1编号） 2写出从图的邻接表表示转换成邻接矩阵表示的算法。3已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 4试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)5令G=（V，E）为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点i至顶点j有一条弧则应使ij。数据结构作业（第七章 图2） 第 2 页 共 5 页