9.3. Quiz

This section provides exercises for better understanding in network flow

Augmenting Paths

An augmenting path is a directed path between the source and target vertices; no need to worry about residuals for this quiz.

Create the NetworkFlowQuiz class under the graph.flow package.
Update the getAugmentingPaths() method that returns all augmenting paths between the specific source and target vertices using depth-first traverse.

Extra Credit

Create the NetworkFlowQuizExtra class and update the getAugmentingPaths() method such that it uses breadth-first traverse instead of depth-first traverse.

Simplex Algorithm

Given the following graph where there are two source vertices, $S_1$ and $S_2$ , and two target vertices, $T_1$ and $T_2$ , define the objective functions and their constraints to find the (1) max-flow and (2) min-cut using the simplex algorithm:

Report

Write quiz8 that includes:

The worst-case complexity of your getAugmentingPaths() method.
An explanation of when the depth-first traverse is preferred over the breadth-first traverse and vice versa to find augmenting paths.
An objective function and is constraints to find max-flow.
An objective function and is constraints to find min-cut.

Previous9.3. Simplex Algorithm Next10. Dynamic Programming

Last updated 2 years ago

Augmenting Paths

An augmenting path is a directed path between the source and target vertices; no need to worry about residuals for this quiz.

Create the NetworkFlowQuiz class under the graph.flow package.

Update the getAugmentingPaths() method that returns all augmenting paths between the specific source and target vertices using depth-first traverse.

Report

Write quiz8 that includes:

The worst-case complexity of your getAugmentingPaths() method.

An explanation of when the depth-first traverse is preferred over the breadth-first traverse and vice versa to find augmenting paths.

An objective function and is constraints to find max-flow.

An objective function and is constraints to find min-cut.