CS5800-Homework 12 Solved

          1      Exercise 26.1-3
Let G = (V,E) be a flow network with a capacity function c. Let s be the source of the network, and let t be the sink. A flow in G is a real-valued function f : V × V → R that satisfies the following two properties:

Capacity constraint: For all u,v ∈ V , we require 0 ≤ f(u,v) ≤ c(u,v) Flow conservation: For all u ∈ V − {s,t}, we require

 

when (u,v) ∈/ E, there can be no flow from u to v, and f(u,v) = 0. We call the nonnegative quantity f(u,v) the flow from vertex u to vertex v. The value |f| of a flow f is defined as

 

that is, the total flow out of the source minus the flow into the source. Typically, a flow network will not have any edges into the source, and the flow into the source, given by the summation Pv∈V f(v,s) will be 0. Since u is a vertex for which there is no path s ⇝ u ⇝ t,f(s,u) = f(u,t) = 0 which means there is no flow in or flow out for vertex u. Since there is no flow passing through u,f(u,v) = f(v,u) = 0 for all vertices v ∈ V .

          2      Exercise 26.1-4
A flow in G is a real-valued function f : V × V → R that satisfies the following two properties:

Capacity constraint: For all u,v ∈ V , we require 0 ≤ f(u,v) ≤ c(u,v)

Flow conservation: For all u ∈ V − {s,t}, we require

 

Since f1 and f2 are flow, we have 0 ≤ f1(u,v) ≤ c(u,v) and 0 ≤ f2(u,v) ≤ c(u,v). Assume for all α in the range 0 ≤ α ≤ 1, we have:

 0*α ≤ αf1(u,v) ≤ αc(u,v)0*(1-α) ≤ (1 − α)f2(u,v) ≤ (1 − α)c(u,v)

0≤ αf1(u,v) ≤ αc(u,v)0≤ (1 − α)f2(u,v) ≤ (1 − α)c(u,v) Let’s make summation for two inequality:

0 + 0 ≤ αf1(u,v) + (1 − α)f2(u,v) ≤ αc(u,v) + (1 − α)c(u,v)

0 ≤ αf1(u,v) + (1 − α)f2(u,v) ≤ c(u,v)

A flow also satisfies Flow conservation: For all u ∈ V − {s,t}, we have:

 P f1(v,u) = Pv∈V f1(u,v)Pv∈V f2(v,u) = Pv∈V f2(u,v) v∈V

αPv∈V f1(v,u) = αPv∈V f1(u,v)(1-α)Pv∈V f2(v,u) = (1 − α)Pv∈V f2(u,v) After summation, we have:

αXf1(v,u) + (1 − α)Xf2(v,u) = αXf1(u,v) + (1 − α)Xf2(u,v)

                                    v∈V                                                                 v∈V                                              v∈V                                                                 v∈V

                                            X                                                      X
                                                       αf1(v,u) + (1 − α)f2(v,u) =              αf1(u,v) + (1 − α)f2(u,v)

                                          v∈V                                                                                                        v∈V

Since αf1+(1−α)f2 satisfies the two properties which are capacity constraint and flow conservation, then the flows in a network from a convex set.

          3      Exercise 26.2-2
 

Figure 1: Figure 26.1 (b)

Flow: 11+1+7+4-4 = 19, Capacity: 16+4+7+4 = 31

          4               Implement Push-Relabel for finding maximum flow

class Node:

def   i n i t   ( s e l f ) : s e l f .h = 0 s e l f . e = 0

def relabel ( s e l f ) : s e l f .h += 1

def push( self , flow ) : s e l f . e += flow

                   def pour( self ,        flow ) :

s e l f . e −= 1

class Graph :

               def      i n i t    ( self ,         node size ) :

 s e l f . size = node size s e l f . node = dict () s e l f . edges = [Node() for i
in range( node  size+1) ]
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

          5        Explain in a brief paragraph
Each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. Vertex heights determine how flow is pushed: we push flow only downhill, that is, from a higher vertex to a lower vertex. The flow from a lower vertex to a higher vertex may be positive, but operations that push flow push it only downhill. We fix the height of the source at |V | and the height of the sink at 0. All other vertex heights start at 0 and increase with time. The algorithm first sends as much flow as possible downhill from the source toward the sink. The amount it sends is exactly enough to fill each outgoing pipe from the source to capacity; that is, it sends the capacity of the cut (s,V − {s}). When flow first enters an intermediate vertex, it collects in the vertex’s reservoir. From there, we eventually push it downhill. Since only pipes that leave a vertex u and are not already saturated with flow connect to vertices that are on the same level as u or are uphill from u, in this case, we must increase its height—an operation called “relabeling” vertex u to rid an overflowing vertex u of its excess flow.