下面关于图(网)的叙述,正确的是(60)。A.连通无向网的最小生成树中,顶点数恰好比边数多1B

Question

下面关于图（网）的叙述，正确的是（60）。

A.连通无向网的最小生成树中，顶点数恰好比边数多1

B.若有向图是强连通的，则其边数至少是顶点数的2倍

C.可以采用AOV 网估算工程的工期

D.关键路径是AOE 网中源点至汇点的最短路径

Answer 1

正确答案：A
本题考查数据结构方面的基础知识。在有向图中，若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网(ActivityOnVertexNetwork,AOV网）。若在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网(ActivityOnEdgeNetwork,AOE网）通常在AOE网中列出了完成预定工程计划所需进行的活动、每项活动的计划完成时间、要发生哪些事件以及这些事件和活动间的关系，从而可以分析该项工程是否实际可行并估计工程完成的最短时间，分析出哪些活动是影响工程进度的关键。进一步可以进行人力、物力的调度和分配，以达到缩短工期的目的。根据生成树的定义，有n个顶点的连通图的生成树恰好有n-1条边。