Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I did this question in a course and it is Consider our algorithm for computing a topological ordering that is based on depth-first search (i.e., NOT the "straightforward solution"). Suppose we run this algorithm on a graph G that is NOT directed acyclic. Obviously it won't compute a topological order (since none exist). Does it compute an ordering that minimizes the number of edges that go backward?

For example, consider the four-node graph with the six directed edges $$(s,v),(s,w),(v,w),(v,t),(w,t),(t,s).$$ Suppose the vertices are ordered $s,v,w,t$. Then there is one backwards arc, the $(t,s)$ arc. No ordering of the vertices has zero backwards arcs, and some have more than one. please help and tell me what it means by saying NOT acyclic?

share|improve this question
add comment

1 Answer 1

This means there is at least one directed cycle in the graph. The language is a bit funny because rather than saying "suppose there is at least one directed cycle", they will probably be saying this to compare it to the usual case where it is directed acyclic.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.