A directed graph is one where each edge has a direction. This is often depicted

Question

A directed graph is one where each edge has a direction. This is often depicted with an arrow from one vertex to another. They can be though of as one-way streets. A directed cycle is a sequence ((x1, x2),(x2, x3), . . . ,(xk?1, xk),(xk, x1)) of directed edges that takes you from one vertex another and eventually returns you to your starting vertex.

A topological sortof a directed graph is an ordering of the vertices where every edge is directed from an earlier vertex to a later vertex. Notice that you can

Explanation / Answer

Suppose there is a directed graph that has both cycle and topological sort

if there are n vertices , vertices will be ordered from 1 to n in the graph

Let earliest vertext in cycle starts at k and last vertext is at k + m both k & k+m <= n

But k+m th vertext last vertext would point to kth vertex( first vertex ) means last vertext comes before first vertext

=> our assumption was wrong

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.