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.