• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

是否允许在CPM/PERT中的图表中强连接组件?

算法 来源:L H 12次浏览

我已经读过,每个非平凡的SCC都是一个循环,这意味着在CPM/PERT方法中使用的图中不应该有任何,但是在我读了其他一些东西之后,我有点困惑:(我真的需要帮助!是否允许在CPM/PERT中的图表中强连接组件?

===========解决方案如下:

PERT图显示一个要采取的行动的部分排序,所以他们不能有个周期。如果一个周期将出席这将意味着,铁,你需要开始一个活动,然后做B,然后C,然后A再次 – 这是没有意义的。也许这会更容易回答,如果你提供一个链接到内容,让你感到困惑。评论): 每个SCC都必须包含循环。证明草图:假设有ex在有向图中没有单个周期的SCC。假设它包含两个顶点:A和B.从the definition of SCC必须存在从A到B以及从B到A的路径。因此,我们总是可以使用这些路径之一从A到B,然后是另一个从B到A的路径(它将是一条不同的路径,因为我们正在考虑一个有向图),从而形成一个循环。这导致矛盾,所以你不能没有周期的SCC。关于我上面的回答,这表明PERT图表不能有SCC。


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)