DOC

Multi-Terminal Maximal Flows

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