Assignment 4
How to cut a graph
Out: Nov 16, 2023.
Given a integer edge-weighted directed graph with two special and distinct vertices
called the source and the terminal, our goal is to find a cut separating the source
and the terminal of the smallest value.
Consider the following examples of graphs:
graph1 (four-vertex example)
and
graph2 (200-vertex example).
Assume the source and the terminal 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 problem using the flow method discussed in class.
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-cut to the optimality of the flow output (optimality proof).
You may work in groups of up to three for this assignment.