CS6515 EXAM 2 2026/2027
ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
Augmenting Path - correct answer-A path that exists on the
residual graph from s -> t.
This type of path implies there exists more flow that can be
pushed through the graph.
This occurs when there exists a path through which the
minimum residual capacity F among all edges in the path is
greater than 0.
When is a flow a max flow - correct answer-When there is no
augmenting path in the residual graph
Size(flow) = - correct answer-F_out(L) - f_in(L)
How to construct a min cut - correct answer-- construct a max
flow
,- set L to be those vertices reachable from s in the residual
graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
Ford-Fulkerson vs Edmonds-Karp - correct answer-FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
- assumes integer capacities
- capacities cannot be infinity
EK:
- Finds augmenting paths using BFS (is an example of FF)
- O(nm^2)
- No assumptions on integer capacities
- Only requires positive capacities
Edmonds-Karp Number of rounds is at most - correct answer--
mn
- Every round residual graph changes by > 1 edge
- Lemma: all edges are deleted/inserted later < n/2 times
- Since m edges, total rounds < nm/2
, BFS Levels - correct answer-- Minimum number of edges from
s to some vertex
- They never decrease in residual network, can only increase
- If we delete an edge and add it back it will increase by at least
2
- Thus, since there are n levels, the maximum number of times
we can delete and add back an edge is n/2
Adding/Removing an Edge to G^f implies - correct answer--
Add: if add y->z, then edge z->y must be on augmenting path
- Remove y ->z, then edge y ->z must be on augmenting path
How to topologically sort a DAG - correct answer-Sort vertices
by decreasing post-order #
Post-order # Properties for DAG - correct answer-- highest post
order # is source
- lowest post order # is sink (this is not always true for general
directed graphs but is always true for DAGs)
ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
Augmenting Path - correct answer-A path that exists on the
residual graph from s -> t.
This type of path implies there exists more flow that can be
pushed through the graph.
This occurs when there exists a path through which the
minimum residual capacity F among all edges in the path is
greater than 0.
When is a flow a max flow - correct answer-When there is no
augmenting path in the residual graph
Size(flow) = - correct answer-F_out(L) - f_in(L)
How to construct a min cut - correct answer-- construct a max
flow
,- set L to be those vertices reachable from s in the residual
graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
Ford-Fulkerson vs Edmonds-Karp - correct answer-FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
- assumes integer capacities
- capacities cannot be infinity
EK:
- Finds augmenting paths using BFS (is an example of FF)
- O(nm^2)
- No assumptions on integer capacities
- Only requires positive capacities
Edmonds-Karp Number of rounds is at most - correct answer--
mn
- Every round residual graph changes by > 1 edge
- Lemma: all edges are deleted/inserted later < n/2 times
- Since m edges, total rounds < nm/2
, BFS Levels - correct answer-- Minimum number of edges from
s to some vertex
- They never decrease in residual network, can only increase
- If we delete an edge and add it back it will increase by at least
2
- Thus, since there are n levels, the maximum number of times
we can delete and add back an edge is n/2
Adding/Removing an Edge to G^f implies - correct answer--
Add: if add y->z, then edge z->y must be on augmenting path
- Remove y ->z, then edge y ->z must be on augmenting path
How to topologically sort a DAG - correct answer-Sort vertices
by decreasing post-order #
Post-order # Properties for DAG - correct answer-- highest post
order # is source
- lowest post order # is sink (this is not always true for general
directed graphs but is always true for DAGs)
