DOC

# Multi-Terminal Maximal Flows

By Alexander Garcia,2014-10-13 15:08
9 views 0
Multi-Terminal Maximal Flows

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

n121 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

Report this document

For any questions or suggestions please email
cust-service@docsford.com