�ݺ�ߣ

Editor's Notes

1. In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum. In a flow network, flow going into a vertex must equal flow going out of a vertex (with the exception of the source node and the sink node, s and t respectively). Thus we cannot accumulate flow anywhere in the network. he Preflow algorithm relaxes this constraint while it determines the maximum flow of the network, allowing a vertex to have more flow coming into it than going out. This is called the excess flow of a vertex, or preflow. Any vertex with excess flow is known as an active vertex.
2. The push-relabel algorithm finds maximum flow on a flow network. There are three conditions for a flow network: Capacity constraints: . The flow along an edge cannot exceed its capacity. Skew symmetry: . The net flow from to must be the opposite of the net flow from to (see example). Flow conservation: , unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow. he push-relabel algorithm finds maximum flow on a flow network. There are three conditions for a flow network: Capacity constraints: . The flow along an edge cannot exceed its capacity. Skew symmetry: . The net flow from to must be the opposite of the net flow from to (see example). Flow conservation: , unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow. The preflow algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the Flow conservation constraint is again observed): Non-negativity constraint: for all nodes . More flow enters a node than exits. Given a flow network with capacity from node u to node v given as , and the flow across u and v given as , source s and sink t, we want to find the maximum amount of flow you can send from s to t through the network. Some key concepts used in the algorithm are: residual edge: If available capacity we have a residual edge . residual edge (Alternate): . We can push flow back along an edge. residual graph: The set of all residual edges forms the residual graph. legal labelling: For each residual edge . We only push from u to v if . excess(u): Sum of flow to and from u. height(u): Each vertex is assigned a height value. For values , the height serves as an estimate of the distance to the sink node t. For values , the height is an estimate of the distance back to the sink s.
3. Push A push from u to v means sending as much excess flow from u to v as we can. Three conditions must be met for a push to take place: is active Or . There is more flow entering than exiting the vertex. There is a residual edge from u to v, where u is higher than v. If all these conditions are met we can execute a Push: Function Push(u,v) flow = min(excess(u), c(u,v)-f(u,v)); excess(u) -= flow; // subtract the amount of flow moved from the current vertex excess(v) += flow; // add the flow to the vertex we are pushing to f(u,v) += flow; // add the amount of flow moved to the flow across the edge (u,v) f(v,u) -= flow; // subtract the flow from the edge in the other direction. Relabel When we relabel a node u we increase its height until it is 1 higher than its lowest neighbour in the residual graph. Conditions for a relabel: is active where So we have excess flow to push, but we not higher than any of our neighbours that have available capacity across their edge. Then we can execute Relabel: Function Relabel(u) height(u) = min(height(v) where r(u,v) > 0) + 1;