Assignment 4
Cuts and Flows
Out: Oct 22, 2020.
Given a capacitated directed graph (where each edge has an integer capacity)
with two distinguished vertices called source s and terminal t,
our goal is to find an s-t flow with maximum value.
Consider the following examples of capacitated graphs:
graph1 (four-vertex example)
and
graph2 (200-vertex example).
Assume s and t are the vertices with smallest and largest indices, respectively.
Both graphs are given in graphviz
format where the labels denote the capacities of the directed edges.
Design a program to solve the maximum flow problem on integral capacitated graphs.
What to Hand-in
Submit via email a single compressed file that contains all your source file(s).
Your program should solve the problem in general but specify your solutions for
the two sample files above. Your program should output the following items:
- The value of the flow found by the algorithm.
- The flow graph which is a graph depicting the output flow of the algorithm. This should be specified in the same
graphviz format as above (placed in an output file) where the labels specify the flow values.
- A witness to the optimality of the output flow (that is, a proof that the output flow is maximum).
You may work in groups of up to three for this assignment.