문제

I have read that every non-trivial SCC is a cycle, which means that in a graph used in CPM/PERT method there shouldn't be any, but after I read some other things, I got a little bit confused :( I really need help!

도움이 되었습니까?

해결책

PERT charts indicate the partial ordering of the actions one wants to take, so they can't have cycles. If a cycle would be present it would mean that, f.e. you need to start with activity A, then do B, then C, and then A again - this doesn't make sense. Maybe it would be easier to answer if you would provide a link to the content that got you confused.

EDIT (regarding the OP's comment): Every SCC must contain cycles. Proof sketch: assume that there exists a SCC without a single cycle in a directed graph. Assume that it contains two vertices: A and B. From the definition of SCC there must exist a path from A to B, and from B to A. So, we always can use one of this paths to travel from A to B, and then the other path to get back from B to A (it will be a different path, because we are considering a directed graph), thus forming a cycle. This leads to a contradiction, so you can't have a SCC without cycles. Regarding my answer above, this suggests that PERT charts can't have SCC's either.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top