 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Maximum Flow
Glossary
| flow-network | A flow-networkG = (V, E) is a directed graph in which each edge
(u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0.
(See page 644)
| | | | | maximum-flow problem | given a flow network G with source s and sink t, and we wish to find a flow of maximum value.
(See page 645)
| | | | | total net flow | at a vertex is defined to be the total positive flow leaving a vertex minus the total positive flow entering a vertex.
(See page 645)
| | | | | implicit summation notation | We shall be dealing with several functions (like f) that take as arguments two vertices in a flow network. In this chapter, we shall use an implicit summation notation in which either argument, or both, may be a set of vertices, with the interpretation that the value denoted is the sum of all possible ways of replacing the arguments with their members.
(See page 648)
| | | | | scalar flow product | Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted αf, is a function from V x V to R defined by (αf)(u, v) = α · f(u, v).
(See page 650)
| | | | | flow sum | The flow sum f1 + f2 is the function from V x V to R defined by (f1 + f2)(u, v) = f1(u, v) + f2(u, v) for all u, v ∈ V.
(See page 650)
| | | | | residual capacity | The amount of additional flow we can push from u to v before exceeding the capacity of c(u, v) is the residual capacity of (u, v), given by cf(u, v) = c(u, v) - f(u, v). The maximum amount by which we can increase the flow on each edge in an augmenting path p is the residual capacity of p, given by cf = min{cf(u, v) : (u, v) is on p}.
(See page 651)
| | | | | residual network | Given a flow network G = (V, E) and a flow of f, the residual network of G induced by f is Gf = (V, Ef), where Ef = {(u, v) ∈ V x V : cf(u, v) > 0}. Each edge of the residual network, or residual edge, can admit a flow that is greater than 0.
(See page 652)
| | | | | augmenting path | Given a flow network G = (V, E) and a flow f, an aumenting path p is a simple path from s to t in the residual network Gf. By the definition of the residual network, each edge (u, v) on an augmenting path admits some additional positive flow from u to v without violating the capacity constraint on the edge. For the Hopcraft-Karp bipartite matching algorithm we say that a simple path P in G is an augmenting path with respect to M if it starts at an unmatched vertex in L, ends at an unmatched vertex in R, and its edges belong alternately to M and E - M. (This definition of an augmenting path is related to, but different from, an augmenting path in a flow network.)
(See page 654)
| | | | | cut | A cut (S, T) of flow network G = (V, E) is a partition of V into S and T = V - S such that s ∈ S and t ∈ T. (This definition is similar to the definition of "cut" that we used for minimum spanning trees in Chapter 23, except that here we are cutting a directed graph rather than an undirected graph, and we insist that s ∈ S and t ∈ T.)
(See page 655)
| | | | | net flow | If f is a flow, then the net flow across the cut (S, T) is defined to be
f(S, T).
(See page 655)
| | | | | capacity | The capacity of the cut (S, T) is c(S, T).
(See page 655)
| | | | | minimum cut | A minimum cut of a network is a cut whose capacity is minimum over all cuts of the network.
(See page 655)
| | | | | Edmonds-Karp algorithm | The bound on FORD-FULKERSON can be improved if we implement the computation of the augmenting path p with a breadth-first search, that is, if the augmenting path is a shortest path from s to t in the residual network, where each edge has unit distance (weight). We call the FORD-FULKERSON method so implemented the Edmonds-Karp algorithm.
(See page 661)
| | | | | critical | An edge (u, v) in a residual network Gf is critical on an augmenting path p if the residual capacity of p is the residual capacity of (u, v), that is, if cf(p) = cf(u, v).
(See page 662)
| | | | | edge connectivity | of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph.
(See page 664)
| | | | | matching | Given an undirected graph G = (V, E), a matching is a subset of edges M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v.
(See page 664)
| | | | | matched | We say that a vertex v ∈ V is matched by matching M if some edge in M is incident on v; otherwise, v is unmatched.
(See page 664)
| | | | | maximum matching | A maximum matching is a matching of maximum cardinality, that is, a matching M such that for any matching M', we have |M| ≥ |M'|.
(See page 664)
| | | | | corresponding flow network | We define the corresponding flow networkG' = (V', E') for the bipartite graph G as follows. We let the source s and sink t be new vertices not in V, and we let V' = V ∪ {s, t}. If the vertex partition of G is V = L ∪ R, the directed edges of G' are the edges of E, directed from L to R, along with V new edges: E' = {(s, u) : u ∈ L}
∪ {(u, v) : u ∈ L, v ∈ R, and (u, v) ∈ E}
∪ {(v, t) : v ∈ R}. To complete the construction, we assign unit capacity to each edge in E'. Since each vertex in V has at least one incident edge, |E| ≥ |V| / 2. Thus, |E| ≤ |E'| = |E| + |V| ≤ 3|E|, and so |E'| = Θ(E).
(See page 665)
| | | | | integer-valued | We say that a flow f on a flow network G = (V, E) is integer-valued if f(u, v) is an integer for all (u, v) ∈ V x V.
(See page 666)
| | | | | perfect matching | A perfect matching is a matching in which every vertex is matched.
(See page 669)
| | | | | neighborhood | For any X ⊆ V, define the neighborhood of X as N(X) = {y ∈ V : (x, y) ∈ E for some x ∈ X}, that is, the set of vertices adjacent to some member of X.
(See page 669)
| | | | | Hall's theorem | there exists a perfect mathing in G if and only if |A| ≤ |N(A)| for every subset A ⊆ L.
(See page 669)
| | | | | d-regular | We say that a bipartite graph G = (V, E), where V = L ∪ R, is d-regular if every vertex v ∈ V has degree exactly d. Every d-regular bipartite graph has a matching of cardinality |L| by arguing that a minimum cut of the corresponding flow network has capacity |L|.
(See page 669)
| | | | | preflow | a function f : V x V → R that satisfies skew symmetry, capacity constraints, and the following relaxation of flow conservation:
f(V, u) ≥ 0 for all vertices u ∈ V = {s}. That is, the total net flow at each vertex other than the source is nonnegative.
(See page 669)
| | | | | excess flow | We call the total net flow at a vertex u the excess flow into u, given by e(u) = f(V, u).
(See page 669)
| | | | | overflowing | We say that a vertex u ∈ V - {s, t} is overflowing if e(u) > 0.
(See page 670)
| | | | | height function | A function h : V → N is a height function if h(s) = |V|, h(t) = 0, and h(u) ≤ h(v) + 1 for every residual edge (u, v ∈ Ef).
(See page 671)
| | | | | push | We call the operation PUSH(u, v) a push from u to v. if a push operation applies to some edge (u, v) leaving a vertex u, we also say that the push operation applies to u.
(See page 672)
| | | | | saturating push | It is a saturating push if edge (u, v) becomes saturated (cf(u, v) = 0 afterward); otherwise, it is a nonsaturating push. if an edge is saturated, it does not appear in the residual network.
(See page 672)
| | | | | relabeled | When we call the operation RELABEL(u), we say that vertex u is relabeled. Note that when u is relabeled, Ef must contain at least one edge that leaves u, so that the minimization in the code is over a nonempty set. This property follows from the assumption that u is overflowing. Since e[u] > 0, we have e[u] = f(V, u) > 0, and hence there must be at least one vertex v such that f[v, u] > 0. But then, cf(u, v) = c(u, v) - f[u, v] = c(u, v) + f[v, u] > 0, which implies that (u, v) ∈ Ef. The operation RELABEL(u) thus gives u the greatest height allowed by the constraints on height functions.
(See page 673)
| | | | | admissible edge | If G = (V, E) is a flow network with source s and sink t, f is a preflow in G, and h is a height function, then we say that (u, v) is an admissible edge if cf(u, v) > 0 and h(u) = h(v) + 1. Otherwise, (u, v) is inadmissible.
(See page 681)
| | | | | admissible network | is Gf, h = (V, Ef,h), where Ef,h is the set of admissible edges. The admissible network consists of those edges through which flow can be pushed.
(See page 681)
| | | | | neighbor list | Given a flow network G = (V, E), the neighbor list N[u] for a vertex
u ∈ V is a singly linked list of the neighbors of u in G.
(See page 683)
| | | | | discharged | An overflowing vertex u is discharged by pushing all of its excess flow through admissible edges to neighboring vertices, relabeling u as necessary to cause edges leaving u to become admissible.
(See page 683)
| | | | | grid | An n x n grid is an undirected graph consisting of n rows and n columns of vertices.
(See page 692)
| | | | | escape problem | Given m ≤ n2 starting points (x1, y1), (x2, y2), . . . , (xm, ym) in the grid, the escape problem is to determine whether or not there are m vertex-disjoint paths from the starting points to any m different points on the boundary.
(See page 692)
| | | | | path cover | of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P.
(See page 692)
| | | | | minimum path cover | of G is a path cover containing the fewest possible paths.
(See page 692)
| | | | | symmetric difference | Given two sets A and B, the symmetric difference A ⊕ B is defined as (A - B) ∪ (B - A), that is the elements that are in exactly one of the two sets.
(See page 696)
|
|
2002 McGraw-Hill Higher Education