Chapter 7. Multi-Terminal Maximal Flows
? 1. Introduction
? So far : on the value of a maximal flow from the source node to the sink node
? shifting this issue to the problem concerned with “from one node to another”
all pairs of nodes ，
consider the method of Gomory and Hu ?
? 2. Forests, Trees, and Spanning subtrees
1. Problem Description :
? Consider undirected graphs :
tree is one of those graphs , where a tree is a connected graph G=[N : A] that
contains no cycles
? In a tree, there is a unique chain ( or path ) joining each pair of nodes
? Forest : A graph, connected or not, without cycles is called a forest
Each connected piece of a “forest” is consequently a “tree” ，
? A tree on n nodes has precisely (n-1) arcs
? Given a connected graph G on n nodes, one can delete arcs from G until a tree
remains Such a (remaining) tree is called a spanning subtree of G ，
? If a graph G and a spanning subtree T of G are specified, we refer to the
arcs of T as in-tree arcs, the others as out-of-tree arcs
if an out-of-tree arc is added to a spanning subtree, the resulting graph ，
has just one cycle
? Suppose that each arc (x,y) of a connected graph G has associated with it a
real number a(x,y) , which may be thought of as the length of (x,y)
Among all the spanning subtree of G, there is then a longest one : that is, ，
one that maximizes the sum of the numbers a(x,y) associated with arcs of
the subtree
; In studying multi-terminal network flows, maximal spanning subtrees will be
useful
?
maximality criterion for a spanning subtree
?
algorithms for constructing maximal spanning subtrees 2. Maximality Criterion for a spanning subtree
necessary conditions ? ，
? Suppose T is a maximal spanning subtree of G
? Let xx,,; be the chain of in-T arcs joining x and x 1k1k
?
(1.1) , where (x,x) is an out-of-T arc axxaxxaxx,min,,,,；;；？；？；？！，1k1121kkk？
Since, otherwise, we could replace one of the in-T arcs of the chain by ：
(x,x) to obtain a longer spanning subtree 1k
? If the condition (1.1) holds for each out-of-T arc, then the spanning subtree ?
T
is maximal
TT If and are two spanning subtrees and satisfy (1.1), then both have ，12
the
same length, “ which implies a sufficiency condition”
Theorem 1.1
A necessary and sufficient condition that a spaning subtree be maximal is that
(1.1) holds for each out-of-tree arc
? How to construct such spanning subtrees?
Kruskal [4] and Prim [6] : directed algorithms based on Theorem 1.1 ，
(i) begin by selecting a longest arc of G
(ii) At the next stage, also select a longest arc from the remaining arcs that
completes no cycle with previously selected arcs
(iii) after (n-1) arcs have been selected , it is done.
6899
4
758
7
7
? 3. Realization Conditions
vxy,? Denote by the maximal flow value from nodes x to y ；？
vxy,vyx, ? Consider an undirected network G, so that = ；？；？
vxx,，~ ? For convenience, let ；？
? Question :
Determine conditions under which a given symmetric function v can be realized
as the flow function of some network
?
Lemma 2.1
If v is the flow function of a network, then for all nodes x.y and z,
(2.1) vxyvxzvzy,min,,,(；？；？；？！，
? A consequence of (2.1) is that if the network has n nodes, then v can have at ，
most (n-1) numerically distinct functional values
vxx,，~ note : Taking eliminates the necessity of insisting that x.y.z be ：；？
distinct in (2.1)
? By induction from (2.1) ;
xx,,;(2.2) where is any sequence of vxxvxxvxx,min,,,,(;；？；？；？！，1k1121kkk？
nodes of the network
? Lemma 2.2
If the non-negative, symmetric function v satisfies (2.1) for all x.y.z, then there is
an undirected network having the flow function v
?
(2.1) necessary & sufficient condition ? In conclusion :
? Let T be a maximal spanning tree of such an undirected network ( or graph ) G
? Then, from (1.1) and (2.2) ; if is the chain of in-tree arcs from to xx,,;x1k1
xk
(2.3) vxxvxxvxxvxx,min,,,,,,，;；？；？；？；？！，112231kkk？
cxyvxy,,， ? Hence, if each in-tree arc is assigned the capacity , while each ；？；？
out-of-tree arc is deleted from the network, then the flow network T has flow
function v
Thus, if v is realizable, it is realizable by a tree ，
? Theorem 2.3
A non-negative symmetric function v is realizable as the flow function of an
undirected network iff v satisfies (2.1) . Moreover, if v is realizable, it is
realizable by a tree
? 4. Equivalent Networks
identifying all cuts also ?
? Question : Determine the flow function v in an efficient manner
; Recall that v is realizable by a tree and v can take on at most (n-1) numerically
different values
? Suppose we call two n-node networks “flow-equivalent” (or just “equivalent”) if
they have the same flow function v
Thus, every network is equivalent to a tree ，
? How to construct a v-maximal spanning tree?
The idea of Gomory & Hu [2] : ，
Use the successive solutions of precisely (n-1) maximal flow problem.
(i) Suppose that a maximal flow problem has been solved with some node S as
) with source, another t as sink, thereby locating a minimal cut (XX,sX?
as tX?
c1y
c2
stc3
c4
c5x
Fig. 3.1
vxy,? Suppose that we wish to find where both x and y are on the same ；？
side on the cut, say both x and y are in X
All the nodes of can be condensed into a single node to which all the X，
arcs of the minimal cut are attached
We call the network so obtained the “condensed” network ?
Lemma 3.1
vxy,： The maximal flow value between two ordinary nodes x and y of ；？
vxy, the condensed network is equal to the maximal flow value in the ；？
original network
? Lemma 3.1 a fundamental role in the Gomory & Hu procedure for ?
constructing an equivalent tree
? Procedure of Gomory-Hu
i) Select two nodes arbitrarily and solve a maximal flow problem between them
? locating a minimal cut (XX,), which is represented by the two-node- ，
connecting arc such as vcXX，,；？1
ii) Next, choose two nodes in X, say, and solve the resulting maximal flow
-condensed network problem in the X
iii) This process is continued until each condensed node has a single node.
?
The resulting tree depicts a graph where each pair of the nodes in the graph is
represented by a maximal flow
?
th Let T be the resulting tree. Then, the number attached to the iarc of the vi
final tree T is the capacity of their arc
Lemma 3.2
The maximal flow value between any two nodes of the original network is
equal to min,,,vvv;, where iii,,,; are arcs of the unique path ；？12riii12r
joining the two nodes in the final tree T
; Remarks on Gomory-Hu procedure
? That way of tree construction rests not only in the fact that “an equivalent
tree” is produced with a minimum effort, but also in the kind of equivalent
tree ; that is , one whose arcs represent the relevant (n-1) cuts in the
original network.
；
However, notice that there are usually many trees equivalent to a network,
and also every flow network is equivalent to a chain
? The structure of such a tree ( produced by the procedure ) corresponds
precisely to the multi-terminal cut structure of the network
Gomory-Hu has called such a tree “cut-tree” of the network ?
? All managerial decisions on the network performance analysis and
promotion can be easily made based on the final cut-tree
Example
324
61
16121
27
4 35
i) Selecting node 1 and 6 ;
132456,,,,, cut ( ) ?；，；，XX
61,32,4,5,6
ii) Consider two nodes 1 and 3 ;
132456,,,,, cut ( ) ?；，；，
86132,4,5,6
iii)
866132,54,6
iv)
8661354,6
7
5
v)
868613546
7
2
? 5. Network Synthesis
1. Problem description
Given a symmetric function (demand or requirement)
define for all pairs of nodes of an n-node network
Construct a feasible network which minimizes some prescribed function of the
arc capacities, for example,
vxyrxyxy,,,,(; (4.1) ；？；？
axycxy,,， (4.2) min ?；？；？xy.
axyayx,,， where ；？；？
cxy, = capacity of arc ；？
v) = flow function ；？
r) = requirement function ；？
?
Note that the network is called “feasible” if its flow function v satisfies (4.1) &
a) is the known cost of installing per unit capacity ；？
? The problem is a linear programming, while the conditions (4.1) can be
n？121？ represented by linear inequalities :
cXXrxy,max,((4.3) ；？；？xXyX??,
corresponding to all cuts of the network
? Gomory-Hu have suggested simplex methods for the program that do not
require an explicit enumeration and usage of all the constraints (4.3), under
axyxy,,,，;1 (in) the situation where ；？
However, it is in a combinatorial approach. ?
2. Combinatorial method of synthesis
? For the method of synthesizing “ a minimal capacity feasible network”, consider
rxy, the example of <Fig. 4.1> ; in which the requirements appear on each ；？
arc.
2
64
35
913
21
3
1
547
Fig. 4.1
i) Let T be a dominant requirement tree ;
that is, a maximal spanning subtree of the requirement graph (network)
ii) The synthesis uses only the dominant requirement tree T
Note : A necessary and sufficient condition that a network be feasible ?
is that (4.1) holds for all arcs of T
For the sufficiency, consider an out-of-T arc (x,z) : ?
from (1.1), (2.2) and (4.1),
vxzvxyvyuvwz,min,,,,,,(;；？；？；？；？！，
(min,,,,,,(((xyyuwz;；？；？；？！，
((xz, , where x,y,u,…,w,z is the chain of in-T ；？
arcs joining x and z.
iii) Synthesis procedure
? T is decomposed into a sum of { a uniform requirement tree } plus T：
{ a reminder } by subtracting { the smallest in-T requirement } from T：：
all other in-T requirements.
? Each remaining nonuniform subtree further decomposed in the same ?
way
? This process is repeated until T has been expressed as a sum of uniform
requirement subtrees
? Finally, each uniform tree of this decomposition is then synthesized by a
cycle through its nodes (in any order), each arc of which has capacity
equal to 1/2 of the (uniform) requirement
?
Clearly, such a cycle will satisfy all requirements of a uniform tree
? And then, the resulting cycles are then superposed to form a network
* G; that is, corresponding arc capacities are added;
Theorem 4.1
* The network is a feasible minimal capacity network G
?
; Remarks :
**? “G is minimal” implies that the sum of the arc capacities of G is
no larger than the corresponding sum for any feasible network
? A consequence of theorem 4.1 ?
axy,，1 The linear program (4.2), (4.3) with all unit costs , ；？
always
has an optimal solution in which arc capacities are either integers or
half-integers, provided the requirements are integers
? In general, there is a super-abundance of minimal capacity networks
that can be obtained from the synthesis procedure, since a uniform
requirement tree can be synthesized by any cycle through its nodes In ?
fact, any combination of two distinct (such) networks
?
From all of these, there is one whose flow function dominates all others ;
vxyvxy,,( that is, a feasible minimal capacity network such that , G；？；？
vxy, where is the flow function for any other feasible minimal capacity ；？
network
？
To construct : Consider the original requirement network and “revise” G