Chapter 14, Problem 1RE

(a)

To determine

To prove: The law of conservation of flow at a andat e.

Explanation of Solution

Proof:

WE have given a directed network set V, the capacity of arc uv denoted $c_{uv}$ and also given two distinguished vertices s and t.

$0\le f_{uv}\le c_{uv}$ for all $u,v\in V$

$\underset{veV}{{\displaystyle \sum f_{uv}}}=\underset{veV}{{\displaystyle \sum f_{uv}}}$ for all $u\in V\backslash \left\{s,t\right\}$

At a,

$\begin{array}{l}\underset{veV}{{\displaystyle \sum f_{uv}}}=f_{ad}+f_{ae}\\ =2+3\\ =5\\ \text{While}\\ \underset{v\in V}{{\displaystyle \sum f_{uv}}}=f_{ae}+f_{be}+f_{ce}\\ =3+1+0\\ =4\end{array}$

(b)

To determine

The value of the indicated flow;

Explanation of Solution

It is well known that, the value of flow

$F=\left\{f_{uv}\right\}$ In a directed network with source s, sink t and vertex set V is the integer

$val\left(F\right)=\underset{veV}{{\displaystyle \sum f_{uv}}}-\underset{veV}{{\displaystyle \sum f_{uv}}}$

That the net amount of flow per unit time leaving the source or, entering the sink.

$\begin{array}{l}val\left(F\right)=\underset{veV}{{\displaystyle \sum f_{uv}}}-\underset{veV}{{\displaystyle \sum f_{uv}}}\\ =f_{sa}+f_{sb}+f_{se}\\ =11\end{array}$

(c)

To determine

The capacity of the $\left(s,t\right)$-cut defined by $S=\{s,a,b\},T=\{c,d,e,f,t\}$. Illustrate Corollary 14.1.5 for this cut.

Explanation of Solution

He capacity of an $\left(s,t\right)-cut\left\{S,T\right\}$ is the sum of the capacities of all arcs from S to T denoted

$\begin{array}{l}cap\left(S,T\right)=\underset{weSveT}{{\displaystyle \sum c_{uv}}}\\ cap\left(S,T\right)=\underset{weSveT}{{\displaystyle \sum c_{uv}}}\end{array}$

Therefore, the capacity of the cut is $=C_{sc}+C_{av}$

(d)

To determine

The flow be increased along the path sbft.

Explanation of Solution

No, the flow cannot be increased along the path sbft because, this path contains bf the saturated arc.

(e)

To determine

Whether the “given flow maximum” or not.

Explanation of Solution

The $\left(s,t\right)$-flow with largest possible value through a given directed network is called a maximum flow.

Therefore the flow is not maximum.