search
Log In
20 votes
3.4k views

Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.

Which of the following is not a topological ordering?

  1. $1$ $2$ $3$ $4$ $5$ $6$
  2. $1$ $3$ $2$ $4$ $5$ $6$
  3. $1$ $3$ $2$ $4$ $6$ $5$
  4. $3$ $2$ $4$ $1$ $6$ $5$
in Algorithms
edited by
3.4k views
0
pls explain again
0
Only 4 topological orders exist for this graph:

123456

132465

123465

132456

5 Answers

26 votes
 
Best answer

Go with vertex with indegree 0. Remove the vertex with all edges going from it. Repeat the procedure.

We see that $3$ cannot come at first because indegree is not $0$. So, D is the answer here.

ALL other options are in Topological order.

Only $1$ and $4$ order matter for this question.


edited by
5 votes

choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges.

after that there are two possibilities remove one by one either vertex 2 or 3. after that there is one possibility remove vertex 4 .after that two possibilities remove either vertex 5 or 6 one by one. the order of vertex we get is called  topological ordering.

here a,b,c are correct but d is wrong. so d is ans

5 votes
The arrow represents which comes after or which comes before i.e a-->b means that a must come before b or b must come after a

Now jump to the given diagram, as it is clear that

i) 2 and 3 must come after 1

ii) 4 must come after 2 and 3 so obvious comes after 1 also

iii) 5 and 6 must come after 4 so obvious must comes after 1,2 and 3 also.

Now follow this step and check with the given options

Hence option D is not correct as 3 does not comes before 1 (point no. i)

NOTE: (2,3) and (5,6) are at same level, therefore their positions can be interchange as in option (A and B) position of 2 and 3 interchanged.
3 votes
choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges.    See option D) it is starting with vertex 3 which is not having indegree as zero so it can not be answer ..

Therefore option D)
0 votes

The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.

Answer:

Related questions

26 votes
5 answers
1
8.9k views
In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by Dijkstra’s algorithm starting from $S$. Warshall’s algorithm. Performing a DFS starting from $S$. Performing a BFS starting from $S$.
asked Sep 22, 2014 in Algorithms Kathleen 8.9k views
45 votes
16 answers
2
16k views
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
asked Jul 6, 2016 in Algorithms Arjun 16k views
25 votes
3 answers
3
4.3k views
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively. What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$? $3$ $2.1875$ $2.25$ $1.9375$
asked Apr 23, 2016 in Algorithms jothee 4.3k views
23 votes
1 answer
4
5.5k views
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$? $0$, $10$, $110$ ... $11$, $10$, $011$, $010$, $001$, $000$ $11$, $10$, $01$, $001$, $0001$, $0000$ $110$, $100$, $010$, $000$, $001$, $111$
asked Sep 22, 2014 in Algorithms Kathleen 5.5k views
...