问题
单项选择题
下面关于图（网）的叙述中，正确的是（）。
A．连通无向网的最小生成树中，顶点数恰好比边数多1
B．若有向图是强连通的，则其边数至少是顶点数的2倍
C．可以采用AOV网估算工程的工期
D．关键路径是AOE网中源点至汇点的最短路径
答案
参考答案：A
解析：
[要点解析] 生成树即极小连通子图，包含图的所有n个节点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。所以A选项正确。
在有向图G中，如果对于每一对顶点Vi, Vj∈V，Vi≠Vj，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。右图为强连通图，但其边数等于顶点数。
AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图。
[*]
AOE网：用顶点表示事件，弧表示活动，权表示活动持续的时间。通常AOE网用来估算工程的完成时间。
关键路径：由于在AOE网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(指路径上各活动持续时间之和，不是路径上弧的数日)，路径最长的路径叫做关键路径。