Rrerku

How can I add custom success page

How to move the player while also allowing forces to affect it

Unbreakable Formation vs. Cry of the Carnarium

Is "plugging out" electronic devices an American expression?

Why is my log file so massive? 22gb. I am running log backups

How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)

What do you call words made from common English words?

Does it makes sense to buy a new cycle to learn riding?

What do the Banks children have against barley water?

Does the average primeness of natural numbers tend to zero?

Re-submission of rejected manuscript without informing co-authors

"My colleague's body is amazing"

Copycat chess is back

Is it legal to have the "// (c) 2019 John Smith" header in all files when there are hundreds of contributors?

What does 'script /dev/null' do?

Is there a familial term for apples and pears?

Domain expired, GoDaddy holds it and is asking more money

Ideas for 3rd eye abilities

If a centaur druid Wild Shapes into a Giant Elk, do their Charge features stack?

What does "enim et" mean?

Is Social Media Science Fiction?

Is Fable (1996) connected in any way to the Fable franchise from Lionhead Studios?

Calculate Levenshtein distance between two strings in Python

Landlord wants to switch my lease to a "Land contract" to "get back at the city"

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 yesterday

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 yesterday

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 yesterday

maksadbekmaksadbek

1185

$endgroup$

share|cite|improve this question

asked yesterday

maksadbekmaksadbek

1185

share|cite|improve this question

asked yesterday

maksadbekmaksadbek

1185

asked yesterday

maksadbekmaksadbek

1185

asked yesterday

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 yesterday

D.W.♦D.W.

103k12129294

$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 yesterday

answered yesterday

Apass.JackApass.Jack

14k1940

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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 yesterday

D.W.♦D.W.

103k12129294

$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 yesterday

D.W.♦D.W.

103k12129294

$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 yesterday

D.W.♦D.W.

103k12129294

$endgroup$

share|cite|improve this answer

answered yesterday

D.W.♦D.W.

103k12129294

answered yesterday

D.W.♦D.W.

103k12129294

answered yesterday

D.W.♦D.W.

103k12129294

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 yesterday

answered yesterday

Apass.JackApass.Jack

14k1940

$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 yesterday

answered yesterday

Apass.JackApass.Jack

14k1940

$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 yesterday

answered yesterday

Apass.JackApass.Jack

14k1940

$endgroup$

share|cite|improve this answer

edited yesterday

answered yesterday

Apass.JackApass.Jack

14k1940

answered yesterday

Apass.JackApass.Jack

14k1940

answered yesterday

Apass.JackApass.Jack

14k1940