25.1.11. Challenges with Arbitrary Graphs

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Think about the property of cycles in graphs.

2. 2.

   What does topological sorting achieve?

   Hint

   Consider how tasks might depend on one another.

3. 3.

   What is the primary characteristic of a Directed Acyclic Graph?

   • It has cycles
   • It has no cycles
   • It can be undirected

   Hint

   Recall the definition of a DAG.

4. 4.

   Is it NP-hard to find the longest path in arbitrary graphs?

   • True
   • False

   Hint

   Think about the implications of cycles.

5. 5.

   Given a directed acyclic graph of 5 vertices and the following edges: (1,2), (1,3), (2,4), (3,4), (4,5). Calculate the longest path and describe how you computed it.

   Hint

   Draw the graph to visualize all potential paths.

6. 6.

   An arbitrary graph includes cycles: If a vertex connects back to itself multiple times, how would you begin to analyze the longest path?

   Hint

   Think about how to handle vertices that lead back to previous nodes.