第08章_网络流和匹配Network_Flows.ppt

Network Flow Maximum Flow Chapter 8: Network Flow Outline and Reading Flow Networks Flow (§8.1.1) Cut (§8.1.2) Maximum flow Augmenting Path (§8.2.1) Maximum Flow and Minimum Cut (§8.2.1) Ford-Fulkerson’s Algorithm (§8.2.2-8.2.3) Sections §8.2.4-8.5 on Matching and Minimum Flow are optional. Flow Network A flow network (or just network) N consists of A weighted digraph G with nonnegative integer edge weights, where the weight of an edge e is called the capacity c(e) of e Two distinguished vertices, s and t of G, called the source and sink, respectively, such that s has no incoming edges and t has no outgoing edges. Example: Flow A flow f for a network N is is an assignment of an integer value f(e) to each edge e that satisfies the following properties: Capacity Rule: For each edge e, 0 ? f (e) ? c(e) Conservation Rule: For each vertex v ? s,t where E-(v) and E+(v) are the incoming and outgoing edges of v, resp. The value of a flow f , denoted |f|, is the total flow from the source, which is the same as the total flow into the sink Example: Maximum Flow A flow for a network N is said to be maximum if its value is the largest of all flows for N The maximum flow problem consists of finding a maximum flow for a given network N Applications Hydraulic systems Electrical circuits Traffic movements Freight transportation Cut A cut of a network N with source s and sink t is a partition c = (Vs,Vt) of the vertices of N such that s ? Vs and t ? Vt Forward edge of cut c: origin in Vs and destination in Vt Backward edge of cut c: origin in Vt and destination in Vs Flow f(c) across a cut c: total flow of forward edges minus total flow of backward edges Capacity c(c) of a cut c: total capacity of forward edges Example: c(c) = 24 f(c) = 8 Flow and Cut Lemma: The flow f(c) across any cut c is equal to the flow value |f| Lemma: The flow f(c) across a cut c is less than or equal to the capacity c(c) of the cut Theorem: The value of any flow is less than or equal to the capaci