in Algorithms recategorized by
665 views
1 vote
1 vote
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.
in Algorithms recategorized by
665 views

1 Answer

0 votes
0 votes

This statement is not true, because the number of bad edges in a directed graph (contains cycles) is varies with different starting vertices and doesn’t always minimizes the bad edges. Selecting different starting points, the topological ordering will give different sequences and the number of bad edges cannot be guaranteed to be the least or same.

The bad side or edge of a graph is nothing but the Back Edge. In the statement minimizing the number of bad edges that are inconsistent with the linear order meaning that the TOPOLOGIAL-SORT(G) will maximize the number of tree edges.

Let us consider the following example.

Consider the graph G consisting of vertices a, b, c and d. let the edges be (a, b), (b, c), (a, c), and (c, a)
image

Suppose, if we start the DFS of TOPOLOGICAL-SORT(G) at vertex ‘a’ and assume that each adjacency list is ordered alphabetically. then Topological order: a, b, c
image

In this case the bad edge are only one i.e. c->a

Now let’s take same graph and the DFS of TOPOLOGICAL-SORT(G) at vertex ‘b’. then the topological order become b, c, a.
image

In this case the bad edge are now two i.e. a->c && a->b

Thus the TOPOLOGICAL-SORT doesn’t always minimizes the number of bad edges.

edited by

Related questions