Trjtdtk

Why is it that the natural deduction method can't test for invalidity?

Will tsunami waves travel forever if there was no land?

A Strange Latex Symbol

Examples of subgroups where it's nontrivial to show closure under multiplication?

Combinable filters

Is there an official tutorial for installing Ubuntu 18.04+ on a device with an SSD and an additional internal hard drive?

Sci fi novel series with instant travel between planets through gates. A river runs through the gates

simple conditions equation

Do I have an "anti-research" personality?

Pass By Reference VS Pass by Value

What do the phrase "Reeyan's seacrest" and the word "fraggle" mean in a sketch?

How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?

Critique of timeline aesthetic

Controversial area of mathematics

Was there a Viking Exchange as well as a Columbian one?

How can the Zone of Truth spell be defeated without the caster knowing?

Does Gita support doctrine of eternal cycle of birth and death for evil people?

Can someone publish a story that happened to you?

How could Tony Stark make this in Endgame?

Stop and Take a Breath!

Why does nature favour the Laplacian?

What happened to Captain America in Endgame?

With a Canadian student visa, can I spend a night at Vancouver before continuing to Toronto?

How do I reattach a shelf to the wall when it ripped out of the wall?

Why CLRS example on residual networks does not follows its formula?

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proofFord-Fulkerson algorithm clarificationLinear programming formulation of cheapest k-edge path between two nodesWhy is it that the flow value can increased along an augmenting path $p$ in a residual network?Maximum flow with Edmonds–Karp algorithmHow would one construct conjunctively local predicate of order k for checking if a shape is Convex?Equivalence of minimum cost circulation problem and minimum cost max flow problemGiven max-flow determine if edge is in a min-cutWhat is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

1

$begingroup$

I am learning algorithms to solve Maximum Flow problem by reading the CRLS book and confused by the following figure:

That is:

A flow in a residual network provides a roadmap for adding flow to the
original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in
the corresponding residual network $G_f$, we define $f uparrow f'$,
the augmentation of flow $f$ by $f'$, to be a function from $V times V$ to
$R$, defined by

$$(f uparrow f')(u, v) = begincases f(u,v) + f'(u, v) - f'(v, u) &
> textif (u,v) $in$ E \ 0 & textotherwise endcases$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ?
If we follow the formula, it must have a flow 5:
$8 + 5 - 8 = 5$

algorithms network-flow

share|cite|improve this question

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

$endgroup$

add a comment | 

1

$begingroup$

I am learning algorithms to solve Maximum Flow problem by reading the CRLS book and confused by the following figure:

That is:

A flow in a residual network provides a roadmap for adding flow to the
original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in
the corresponding residual network $G_f$, we define $f uparrow f'$,
the augmentation of flow $f$ by $f'$, to be a function from $V times V$ to
$R$, defined by

$$(f uparrow f')(u, v) = begincases f(u,v) + f'(u, v) - f'(v, u) &
> textif (u,v) $in$ E \ 0 & textotherwise endcases$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ?
If we follow the formula, it must have a flow 5:
$8 + 5 - 8 = 5$

algorithms network-flow

share|cite|improve this question

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

$endgroup$

add a comment | 

$begingroup$

I am learning algorithms to solve Maximum Flow problem by reading the CRLS book and confused by the following figure:

That is:

A flow in a residual network provides a roadmap for adding flow to the
original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in
the corresponding residual network $G_f$, we define $f uparrow f'$,
the augmentation of flow $f$ by $f'$, to be a function from $V times V$ to
$R$, defined by

$$(f uparrow f')(u, v) = begincases f(u,v) + f'(u, v) - f'(v, u) &
> textif (u,v) $in$ E \ 0 & textotherwise endcases$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ?
If we follow the formula, it must have a flow 5:
$8 + 5 - 8 = 5$

algorithms network-flow

share|cite|improve this question

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

$endgroup$

share|cite|improve this question

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

share|cite|improve this question

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

asked Apr 7 at 15:52

maksadbekmaksadbek

1185

2 Answers
2

active

oldest

votes

4

$begingroup$

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s to v_2 to v_3 to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

share|cite|improve this answer

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

$endgroup$

add a comment | 

3

$begingroup$

It is explained in part (b) of the caption of Figure 26.4.

The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $fuparrow f'$ in (c), we have
$$ (fuparrow f')(v_2, v_3)=f(v_2,v_3)+f'(v_2,v_3) = 8+4=12.$$

share|cite|improve this answer

edited Apr 7 at 17:52

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106608%2fwhy-clrs-example-on-residual-networks-does-not-follows-its-formula%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s to v_2 to v_3 to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

share|cite|improve this answer

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

$endgroup$

add a comment | 

4

$begingroup$

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s to v_2 to v_3 to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

share|cite|improve this answer

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

$endgroup$

add a comment | 

$begingroup$

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s to v_2 to v_3 to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

share|cite|improve this answer

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

$endgroup$

share|cite|improve this answer

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

answered Apr 7 at 17:50

D.W.♦D.W.

104k14131299

3

$begingroup$

It is explained in part (b) of the caption of Figure 26.4.

The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $fuparrow f'$ in (c), we have
$$ (fuparrow f')(v_2, v_3)=f(v_2,v_3)+f'(v_2,v_3) = 8+4=12.$$

share|cite|improve this answer

edited Apr 7 at 17:52

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

$endgroup$

add a comment | 

3

$begingroup$

It is explained in part (b) of the caption of Figure 26.4.

The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $fuparrow f'$ in (c), we have
$$ (fuparrow f')(v_2, v_3)=f(v_2,v_3)+f'(v_2,v_3) = 8+4=12.$$

share|cite|improve this answer

edited Apr 7 at 17:52

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

$endgroup$

add a comment | 

$begingroup$

It is explained in part (b) of the caption of Figure 26.4.

The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $fuparrow f'$ in (c), we have
$$ (fuparrow f')(v_2, v_3)=f(v_2,v_3)+f'(v_2,v_3) = 8+4=12.$$

share|cite|improve this answer

edited Apr 7 at 17:52

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

$endgroup$

share|cite|improve this answer

edited Apr 7 at 17:52

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940

answered Apr 7 at 17:51

Apass.JackApass.Jack

14.7k1940