3. (15 points) Finding the topological order: By implementation of the decrease-

Question

3. (15 points) Finding the topological order: By implementation of the decrease-and-conquer technique: repeatedly, identify in a remaining digraph a source, which is a vertex with no incoming edges, and delete it along with all the edges outgoing from it. The order in which the vertices are deleted yields a solution to the topological sorting problem. The key step here is to find the source, is it possible that a nonempty dag have no sources? Prove your claim. (hint: use a proof by contradiction)

Explanation / Answer

Answer:-

The structure of equivalent forests can be more difficult than for undirected graphs. Therefore, even for the simple example, the depth-first search forest exhibits all four types of edges possible in a DFS forest of a directed graph:

(i)tree edges (ab, bc, de)

(ii) back edges (ba) from vertices to their ancestors

(iii) forward edges (ac) from vertices to their descendants in the tree other than their children

(iv)cross edges (dc),

Note that a back edge in a DFS forest of a directed graph can connect a vertex to its parent. Either or nor, the presence of a back edge indicates that the digraph has a directed cycle. A directed cycle in a digraph is a sequence of three or more of its vertices that starts and ends with the same vertex and in which every vertex is connected to its immediate predecessor by an edge directed from the predecessor to the successor. For example, a, b, a is a directed cycle in the digraph. Equally, if a DFS forest of a digraph has no back edges, the digraph is a dag, an acronym for directed acyclic graph.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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