Why CLRS example on residual networks does not follows its formula? The 2019 Stack Overflow...
What is the meaning of Triage in Cybersec world?
How to create dashed lines/arrows in Illustrator
Where does the "burst of radiance" from Holy Weapon originate?
Why can Shazam do this?
Idiomatic way to prevent slicing?
What are the motivations for publishing new editions of an existing textbook, beyond new discoveries in a field?
Does light intensity oscillate really fast since it is a wave?
How was Skylab's orbit inclination chosen?
How can I fix this gap between bookcases I made?
It's possible to achieve negative score?
Inflated grade on resume at previous job, might former employer tell new employer?
Spanish for "widget"
Does it makes sense to buy a new cycle to learn riding?
How to change the limits of integration
What does Linus Torvalds means when he says that git "never ever" tracks a file?
How to deal with fear of taking dependencies
Is there a name of the flying bionic bird?
How to reverse every other sublist of a list?
Where to refill my bottle in India?
How are circuits which use complex ICs normally simulated?
Any good smartcontract for "business calendar" oracles?
Access elements in std::string where positon of string is greater than its size
Is this food a bread or a loaf?
Is "plugging out" electronic devices an American expression?
Why CLRS example on residual networks does not follows its formula?
The 2019 Stack Overflow Developer Survey Results Are InWhy 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?
$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) = begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> text{if (u,v) $in$ E} \ 0 & text{otherwise} end{cases}$$
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
asked 2 days ago
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) = begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> text{if (u,v) $in$ E} \ 0 & text{otherwise} end{cases}$$
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
asked 2 days ago
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) = begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> text{if (u,v) $in$ E} \ 0 & text{otherwise} end{cases}$$
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
asked 2 days ago
maksadbekmaksadbek
1185
$endgroup$
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) = begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> text{if (u,v) $in$ E} \ 0 & text{otherwise} end{cases}$$
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
algorithms network-flow
asked 2 days ago
maksadbekmaksadbek
1185
asked 2 days ago
maksadbekmaksadbek
1185
asked 2 days ago
maksadbekmaksadbek
1185
asked 2 days ago
maksadbekmaksadbek
1185
asked 2 days ago
maksadbekmaksadbek
1185
1185
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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$.
answered 2 days ago
D.W.♦D.W.
103k12129294
$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.$$
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
$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
});
}
});
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
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$.
answered 2 days ago
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$.
answered 2 days ago
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$.
answered 2 days ago
D.W.♦D.W.
103k12129294
$endgroup$
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$.
answered 2 days ago
D.W.♦D.W.
103k12129294
answered 2 days ago
D.W.♦D.W.
103k12129294
answered 2 days ago
D.W.♦D.W.
103k12129294
answered 2 days ago
D.W.♦D.W.
103k12129294
103k12129294
add a comment |
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.$$
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
$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.$$
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
$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.$$
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
$endgroup$
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.$$
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
edited 2 days ago
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
answered 2 days ago
Apass.JackApass.Jack
14.1k1940
14.1k1940
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
