min cut

there is an edge-weighted digraph, source vertex s, and target vertex t.
each edge has a positive capacity.
a st-cut is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.
its capacity is the sum of the capacities of the edges from A to B.
minimum cut problem is find a cut of minimum capacity.

image.png

max flow

an st-flow is an assignment of values to the edges such that:
capacity constraint: 0 <= edge's flow <= edge's capacity
local equilibrium: inflow = outflow at every vertex (except s and t)
maximum st-flow problem is to find a flow of maximum value

image.png

image.png

how to find max flow

ford-fulkerson algorithm

image.png

find an undirected path from s to t such that it can increase flow on forward edges(not full), can decrease flow on backward edge(not empty)

image.png

image.png

all paths from s to t are blocked by either, full forward edge or empty backward edge.

image.png

image.png

relationship between flows and cuts

Value of the maxflow = capacity of mincut

image.png

performance

image.png

bad news is that even wehn edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow

image.png

FF performance depends on choice of augmenting paths

image.png

implementation

image.png

image.png

image.png

bipartite matching problem

image.png

image.png

QUIZ

Q1 Fattest path

image.png

this problem could be solved by two way.

1. binary search
   design a linear-time subroutine that takes a real-number T and determines if there is a path from s to t of bottleneck capacity greater than or equal to T.
   because the bottleneck is in the range of min edge and max edge. so we could use binary search on it.
   the check method spend O(E) time, we just iterate from s go every possible point if there is an edge meet the weight, if we found we could enter destination, we know this weight is valid, and we can try bigger weight. ( we want to find the max bottleneck)

this solution could be seen in solution project.

2. Dijkstra
   the relax operation is to fatter the path as much as possible. because we need to find the fattest path. every time we pop the Max Position, to run dijktra algorithm.

this solution could be seen in test

Q2 Perfect matchings in k-regular bipartite graphs

image.png

this question could be used to practice implementing fordfulkerson with int[][] graph.
check the max flow is equal to n, (men + women equal to 2 n)

Q3 Maximum weight closure problem

image.png

if we use some point, we have to contain all the point this vertex point out. we need to check it is deserved. so we only fetch the point which bring its neighbor, the weight is still positive component. to achieve that , we could build a graph, if we found negative paths is larger or equal to the positive paths, we just discard them. in max flow, it is a full path by the positive capacity, if positive is larger than negative, it is a full path by negative capacity. so we need to sum all the positive path then minus the max flow, it is the answer.
we add a source to link all the positive vertex, and assign a target be linked by all the negative vertex; assign edge (v, w) a weight of infinity if there is an edge from v to w in the original digraph.

the brute force solution is to considerate all the situation including add or discard this vertex, get the max from them.

Project Baseball Elimination

image.png

to solve this problem , we will build a flow network like above picture.
source vertex connect to all the matches info, and team vertex connect to target vertex. except the target team.
so the max flow means we need to find a maxflow which can as much as possible use the flow on the edge to the target to make the game left can be used up.
after we calculate the min cut and max flow. we could just compare the value to the total remaining games, if it is same, the team have possibility to win.

possible progress step

Write code to read in the input file and store the data.

Draw by hand the FlowNetwork graph that you want to construct for a few small examples. Write the code to construct the FlowNetwork, print it out using the toString() method, and and make sure that it matches your intent. Do not continue until you have thoroughly tested this stage.

Compute the maxflow and mincut using the FordFulkerson data type. You can access the value of the flow with the value() method; you can identify which vertices are on the source side of the mincut with the inCut() method.

The BaseballElimination API contains the public methods that you will implement. For modularity, you will want to add some private helper methods of your own.

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226