CPM/PERT의 그래프에 강하게 연결된 구성 요소가있을 수 있습니까?

Question

나는 모든 사소한 SCC가 사이클이라는 것을 읽었습니다. 이것은 CPM/PERT 방법에 사용 된 그래프에서 어떤 것이 없어야한다는 것을 의미합니다.하지만 다른 것을 읽은 후에는 조금 혼란스러워합니다.

Answer 1

PERT 차트는 수행 할 작업의 부분 순서를 나타내므로주기를 가질 수 없습니다. 사이클이있을 경우 활동 A부터 시작해야합니다. , B를 누른 다음 C를 누른 다음 다시 A - 이해가되지 않습니다. 혼란스러워하는 콘텐츠에 대한 링크를 제공하면 대답하기가 더 쉬울 수도 있습니다.

EDIT 주석) : 모든 SCC는 사이클을 포함해야합니다. 증명 스케치 : ex 지향 그래프에서 단일주기가없는 SCC입니다. A와 B의 두 개의 정점이 있다고 가정하십시오. the definition of SCC에서 A에서 B까지 그리고 B에서 A까지의 경로가 있어야합니다. 따라서 우리는 항상이 경로 중 하나를 사용하여 A에서 B로 이동 한 다음 다른 경로 B에서 A로 돌아갈 경로 (방향이 지정된 그래프를 고려하고 있기 때문에 다른 경로가 될 것입니다.) 따라서 사이클을 형성합니다. 이것은 모순으로 이어 지므로 사이클없이 SCC를 가질 수는 없습니다. 위의 내 대답에 관해서는 PERT 차트에서 SCC를 가질 수 없음을 나타냅니다.