Let G = (V, E) be a complete directed acyclic graph that has an edge between eve

Question

Let G = (V, E) be a complete directed acyclic graph that has an edge between every pair of vertices and whose vertices are labeled 1, 2, ..., n, where n = |V|. To determined the direction of an edge between two vertices in V, you are only allowed to ask a query. A query consists of two specified vertices u and v and is answered as follows: "from u to v" if (u, v) elementof E, or "from v to u" if (v, u) 6 E Give a worse-case lower bound (as a function of n) for the number of queries required to find a topological sort of G.

Explanation / Answer

Things to note are:-

1. Graph is complete
2. There exists ordering between every pair of vertices.
3. By asking a query we are establishing some kind of Ordering between two nodes i.e from u to v means u > v and vice versa

So from the point 3 and using the Hint given, we can find Topological sort using Comparison based Sorting
Lets see How ?

Run a sorting algorithm and in the comparison section use query i.e Comparing Two vertices by asking the query we can know whether u>v or v>u . The output will have the Ordering of all the vertices where the first node will be the one whose indegree is 0 and the last node will be the one whose outdegree is 0 , Hence we get the output of Topological Sort

Worst Case lower bound

In comparsion based sort the Worst Case lower bound is (nlogn), hence to find the topological sort the lower bound is nlogn

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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