Practice Dependency Graphs in Math
Use these practice problems to test your method after reviewing the concept explanation and worked examples.
Quick Recap
A dependency graph is a directed graph where nodes are variables and arrows show which variables directly influence which others.
Like a flowchart: A affects B, B affects C. Arrows show dependencies.
Example 1
easyThree tasks have the following dependencies: Task B depends on Task A, and Task C depends on Task B. Draw the dependency graph and determine a valid execution order.
Example 2
mediumGiven the dependencies: D depends on A and B; E depends on B and C; F depends on D and E. Find all valid topological orderings.
Example 3
mediumTasks A \to B, A \to C, B \to D, C \to D. What is the minimum number of stages to complete all tasks if independent tasks can run in parallel?
Example 4
mediumA project has tasks with dependencies: B depends on A; C depends on A; D depends on B and C. What is the minimum number of time steps needed if independent tasks can run in parallel?
Example 5
hardGiven the dependency graph with edges A \to C, A \to D, B \to D, B \to E, C \to F, D \to F, E \to F, determine whether adding the edge F \to A would create a problem, and explain why.