题26

题26

题目

Q:在求 AOE 网的关键路径时,若该有向图用邻接矩阵表示且第 列值全为 ,则 ( ).
A. 若关键路径存在,第 个顶点一定是起点
B. 若关键路径存在,第 个顶点一定是终点
C. 关键路径不存在
D. 该有向图对应的无向图存在多个连通分量

分析

A:我认为是这样的
用邻接矩阵来表示图，比如，第j行，第i列，这上面有值，也就是有从j到i的边
如果第 列值全为 ，说明没有从其他点到第 个顶点的边，
那么这和这个点是起点还是终点有什么关系呢？

解

A
邻接矩阵第 列值全为 ,说明顶点 没有入边,为整个工程的开始,若关键路径存在,则该顶点一定是起点。
不能确定关键路径是否存在, 也不能确定其对应的无向图的连通分量个数。