Question

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!

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top