2.6 Directed Acyclic Graphs (DAGs) & Scheduling

DAGs


  1. Which of the following graph features may NOT appear in a digraph:

    Exercise 1


  2. Let \(V\) be a DAG and \(U\) be the DAG with only the covering edges of \(V\). Then,

    1. compared to the length of the shortest path between two nodes in \(V\), the length of the shortest path in \(U\) between these nodes is:

      Exercise 2
    2. compared to the length of the longest path between two nodes in \(V\), the length of the longest path in \(U\) between these nodes is:

      Exercise 3