我已经读过每个重要的 SCC 都是一个循环，这意味着在 CPM/PERT 方法中使用的图表中不应该有任何循环，但是在我阅读了一些其他内容之后，我有点困惑 :( 我真的需要帮忙！
问问题
110 次
1 回答
1
PERT 图表示人们想要采取的行动的部分顺序，因此它们不能有循环。如果存在一个循环，则意味着您需要从活动 A 开始，然后执行 B，然后执行 C，然后再次执行 A-这没有意义。如果您提供指向让您感到困惑的内容的链接，也许会更容易回答。
编辑（关于 OP 的评论）：每个 SCC 都必须包含循环。证明草图：假设有向图中存在一个没有单环的SCC。假设它包含两个顶点：A 和 B。根据SCC 的定义，肯定存在一条从 A 到 B 和从 B 到 A 的路径。因此，我们总是可以使用其中一条路径从 A 到 B，并且然后从 B 回到 A 的另一条路径（这将是一条不同的路径，因为我们正在考虑一个有向图），从而形成一个循环。这会导致矛盾，因此您不能拥有没有周期的 SCC。关于我上面的回答，这表明PERT图表也不能有SCC。
于 2013-08-04T14:21:28.540 回答