DOC

Multi-Terminal Maximal Flows

By Alexander Garcia,2014-10-13 15:08
7 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