自明ではないすべての SCC はサイクルであることを読みました。つまり、CPM/PERT メソッドで使用されるグラフにはサイクルがあるべきではありませんが、他のことを読んだ後、少し混乱しました :( 本当に助けが必要！
1 に答える
1
PERT 図は、実行したいアクションの部分的な順序を示すため、サイクルを持つことはできません。サイクルが存在する場合、アクティビティ A から始めて、次に B、C、そして A をもう一度行う必要があることを意味します。これは意味がありません。混乱したコンテンツへのリンクを提供していただけると、回答しやすいかもしれません。
編集（OPのコメントに関して）：すべてのSCCにはサイクルが含まれている必要があります。証明スケッチ: 有向グラフに 1 つのサイクルのない SCC が存在すると仮定します。2 つの頂点 A と B が含まれていると仮定します。SCCの定義から、A から B へのパス、および B から A へのパスが存在する必要があります。したがって、常にこのパスの 1 つを使用して A から B に移動できます。次に、B から A に戻るもう 1 つのパス (有向グラフを考慮しているため、別のパスになります)、したがってサイクルが形成されます。これは矛盾につながるため、サイクルのない SCC を持つことはできません。上記の私の回答に関して、これは PERT 図にも SCC を含めることができないことを示唆しています。
于 2013-08-04T14:21:28.540 に答える