Exercises 26.1-9

Construct a graph G=(V,E), which V is the set of corners, (u,v)∈E if corner u and corner v is adjacent. Let the capacity of every edge is 1. If there is a network flow larger then 1 from home to school, then there exists two edge-disjoint path.

Exercises 26.1-8

Given a graph G = (V,E) with source s, sink t and capacity constraint c(u,v). We assign an flow variable for every edge (u,v). The linear programming formulation is

.

such that

.

Exercises 26.1-7

We can prove that the scalar flow product can’t violate the three constraints.

Capacity constraint:

Skew symmetry: obviously

FLow conservation: obviously

Exercises 26.1-6

Capacity constraint.

Exercises 26.1-5

X = s, Y = . f(X,Y) = 0 = f(V-X,Y)

Exercises 26.1-4

It can be proved easily by the definition.

Exercises 26.1-3

Let flow F be the multiple-source flow, F’ be the flow with supersource. The source s in F will has only one in-edge in the F’. Flow in this edge is the summation of all out-edges’ flow, otherwise the flow conservation property is not preserved. Hence F’ is a valid flow.

Exercises 26.1-2

By skew symmetry and flow conservation properties.

Exercises 26.1-1

Since (u,v)∉E, c(u,v) = 0. Hence f(u,v)≤c(u,v)=0, f(u,v)=0.