1
$\begingroup$

Is it true, that the number of edges in residual network is always less than twise the number of edges in the original flow network? My thoughts, that it's false, because in residual network quantity of edges is always $2 * E_{G_{f}}$, even some of them are zero edges. Am I right?

$\endgroup$
1
$\begingroup$

There are different (equivalent) definitions of residual networks (depending on whether you keep edges with capacity $0$ or not).

Anyway, the claim is false since we can select the original network as a graph with no edges (meaning that the only feasible flow is the empty flow, as long as the source and the sink vertices are distinct). Then, the residual network is the graph itself which clearly cannot have less than $0$ edges.

$\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.