2
$\begingroup$

I would like a review for my algorithm for the following question:
A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$ Let G be a balanced network in which in-degree(s)=out-degree(t)=0
Find max-flow for G. My Algorithm so far:

  1. We will define the following capacity-function: $∀(u,v)∈E,f(ⅇ)=c(ⅇ)$
  2. Run over the adj. list and update for every edge it to be our function, and return c(e)

I was also wondering how to prove its a max flow in the correctness part Thank you

$\endgroup$
0
1
$\begingroup$
  1. The flow defined by you, satisfies both the constraints: a) conservation of flow at each vertex -- by the definition of balanced network and b) the capacity constraint because $f_{e} = c_{e}$ for every $e \in E$. Therefore, it is a valid flow.

  2. It is a max-flow because it is sending the flow of value which is equal to the capacity of the cut $C$ defined as: $\{s\}$ and $V \setminus \{s\}$, i.e. max-flow = $\sum_{(s,u) \in E} c(u,v)$ since there is no incoming edge to $s$. Note that any flow can not exceed the capacity of this cut. This fact follows from the min-cut max-flow theorem. i.e., max-flow $=$ min capacity of an $s$-$t$ cut $\leq$ capacity of cut $C$. Therefore, what we have is a max-flow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.