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
when to terminate?
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
add this implementation in extra credit
image.png
QUIZ
Q1 Fattest path
image.png
this problem could be solved by two way.
- 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.
- 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
网友评论