23.2.7. Existence of Vertex with Indegree 0

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Think about what 'acyclic' means.

2. 2.

   What does indegree represent in a graph?

   Hint

   Consider the direction of the edges.

3. 3.

   What does DAG stand for?

   • Directed Alternating Graph
   • Distributed Asynchronous Graph
   • Directed Acyclic Graph

   Hint

   The acronym includes 'Acyclic'.

4. 4.

   True or False: Every directed graph must have at least one vertex with indegree greater than 0.

   • True
   • False

   Hint

   Think about independent vertices.

5. 5.

   Given a DAG representing tasks: Task A must be completed before Task B, and Task B must be completed before Task C. Can you suggest a topological ordering of these tasks?

   Hint

   List the tasks starting from no dependencies.

6. 6.

   Consider a more complex DAG with tasks A through E with the dependencies A -> B, A -> C, B -> D, and C -> D and D -> E. What is one valid topological order?

   Hint

   Follow the dependency chains while sorting.