Individual components of flow along edges in a graph
$begingroup$
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = {V,E}$ with vertices $v in V$ and directed edges $e_{i,j} in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.
Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:
I want to know the number of cars that traveled from $i rightarrow j rightarrow k$. So of all the cars that traveled from $i rightarrow j$, I want to know the number of cars that also traveled from $j rightarrow k$. Can this problem be solved? Could we add certain assumptions to make the problem feasible? For example, if I assume that the net flow at each node is 0, in other words, $sum_j e_{i,j} = sum_j e_{j,i}$.
Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this?
If we consider only the path $1 rightarrow 2 rightarrow 4$ then of the 10 cars that travel from $1 rightarrow 2$, let $x_1$ go back from $2 rightarrow 1$ and the remaining $x_2$ go from $2 rightarrow 4$. Similarly, of the 3 cars going from $4 rightarrow 2$, let $y_1$ go back from $2 rightarrow 4$ and the remaining $y_2$ go from $2 rightarrow 1$. The total flow from $2 rightarrow 1$ and $2 rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations:
$$ x_1 + x_2 = 10, \ y_1 + y_2 = 3, \ x_1 + y_2 = 5, \ x_2 + y_1 = 8, \ x_1, x_2, y_1, y_2 geq 0.$$
This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?
graph-theory network-flow
$endgroup$
add a comment |
$begingroup$
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = {V,E}$ with vertices $v in V$ and directed edges $e_{i,j} in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.
Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:
I want to know the number of cars that traveled from $i rightarrow j rightarrow k$. So of all the cars that traveled from $i rightarrow j$, I want to know the number of cars that also traveled from $j rightarrow k$. Can this problem be solved? Could we add certain assumptions to make the problem feasible? For example, if I assume that the net flow at each node is 0, in other words, $sum_j e_{i,j} = sum_j e_{j,i}$.
Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this?
If we consider only the path $1 rightarrow 2 rightarrow 4$ then of the 10 cars that travel from $1 rightarrow 2$, let $x_1$ go back from $2 rightarrow 1$ and the remaining $x_2$ go from $2 rightarrow 4$. Similarly, of the 3 cars going from $4 rightarrow 2$, let $y_1$ go back from $2 rightarrow 4$ and the remaining $y_2$ go from $2 rightarrow 1$. The total flow from $2 rightarrow 1$ and $2 rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations:
$$ x_1 + x_2 = 10, \ y_1 + y_2 = 3, \ x_1 + y_2 = 5, \ x_2 + y_1 = 8, \ x_1, x_2, y_1, y_2 geq 0.$$
This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?
graph-theory network-flow
$endgroup$
add a comment |
$begingroup$
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = {V,E}$ with vertices $v in V$ and directed edges $e_{i,j} in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.
Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:
I want to know the number of cars that traveled from $i rightarrow j rightarrow k$. So of all the cars that traveled from $i rightarrow j$, I want to know the number of cars that also traveled from $j rightarrow k$. Can this problem be solved? Could we add certain assumptions to make the problem feasible? For example, if I assume that the net flow at each node is 0, in other words, $sum_j e_{i,j} = sum_j e_{j,i}$.
Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this?
If we consider only the path $1 rightarrow 2 rightarrow 4$ then of the 10 cars that travel from $1 rightarrow 2$, let $x_1$ go back from $2 rightarrow 1$ and the remaining $x_2$ go from $2 rightarrow 4$. Similarly, of the 3 cars going from $4 rightarrow 2$, let $y_1$ go back from $2 rightarrow 4$ and the remaining $y_2$ go from $2 rightarrow 1$. The total flow from $2 rightarrow 1$ and $2 rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations:
$$ x_1 + x_2 = 10, \ y_1 + y_2 = 3, \ x_1 + y_2 = 5, \ x_2 + y_1 = 8, \ x_1, x_2, y_1, y_2 geq 0.$$
This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?
graph-theory network-flow
$endgroup$
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = {V,E}$ with vertices $v in V$ and directed edges $e_{i,j} in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.
Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:
I want to know the number of cars that traveled from $i rightarrow j rightarrow k$. So of all the cars that traveled from $i rightarrow j$, I want to know the number of cars that also traveled from $j rightarrow k$. Can this problem be solved? Could we add certain assumptions to make the problem feasible? For example, if I assume that the net flow at each node is 0, in other words, $sum_j e_{i,j} = sum_j e_{j,i}$.
Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this?
If we consider only the path $1 rightarrow 2 rightarrow 4$ then of the 10 cars that travel from $1 rightarrow 2$, let $x_1$ go back from $2 rightarrow 1$ and the remaining $x_2$ go from $2 rightarrow 4$. Similarly, of the 3 cars going from $4 rightarrow 2$, let $y_1$ go back from $2 rightarrow 4$ and the remaining $y_2$ go from $2 rightarrow 1$. The total flow from $2 rightarrow 1$ and $2 rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations:
$$ x_1 + x_2 = 10, \ y_1 + y_2 = 3, \ x_1 + y_2 = 5, \ x_2 + y_1 = 8, \ x_1, x_2, y_1, y_2 geq 0.$$
This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?
graph-theory network-flow
graph-theory network-flow
edited Jan 7 at 7:28
Glorfindel
3,41981830
3,41981830
asked Nov 15 '12 at 18:19
MustafaMustafa
14817
14817
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Usually the definition of a flow implies that the net flow on any vertex is $0$ except for the source or sink. Then, if you compute a maximum flow through your graph, you can force that either the flow on $(u, v)$ or the flow on $(v, u)$ is $0$. Then, if I understood correctly, what you are looking for is simply the flow on a path (i.e. the minimum value of the flow along the edges of this path). It might also be interesting for you to know that if all the capacities are integer, the maximum flow can be decomposed in paths of unit flows (i.e. full paths from source to sink, each one representing one car, although there will not be unicity there).
$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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f238127%2findividual-components-of-flow-along-edges-in-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Usually the definition of a flow implies that the net flow on any vertex is $0$ except for the source or sink. Then, if you compute a maximum flow through your graph, you can force that either the flow on $(u, v)$ or the flow on $(v, u)$ is $0$. Then, if I understood correctly, what you are looking for is simply the flow on a path (i.e. the minimum value of the flow along the edges of this path). It might also be interesting for you to know that if all the capacities are integer, the maximum flow can be decomposed in paths of unit flows (i.e. full paths from source to sink, each one representing one car, although there will not be unicity there).
$endgroup$
add a comment |
$begingroup$
Usually the definition of a flow implies that the net flow on any vertex is $0$ except for the source or sink. Then, if you compute a maximum flow through your graph, you can force that either the flow on $(u, v)$ or the flow on $(v, u)$ is $0$. Then, if I understood correctly, what you are looking for is simply the flow on a path (i.e. the minimum value of the flow along the edges of this path). It might also be interesting for you to know that if all the capacities are integer, the maximum flow can be decomposed in paths of unit flows (i.e. full paths from source to sink, each one representing one car, although there will not be unicity there).
$endgroup$
add a comment |
$begingroup$
Usually the definition of a flow implies that the net flow on any vertex is $0$ except for the source or sink. Then, if you compute a maximum flow through your graph, you can force that either the flow on $(u, v)$ or the flow on $(v, u)$ is $0$. Then, if I understood correctly, what you are looking for is simply the flow on a path (i.e. the minimum value of the flow along the edges of this path). It might also be interesting for you to know that if all the capacities are integer, the maximum flow can be decomposed in paths of unit flows (i.e. full paths from source to sink, each one representing one car, although there will not be unicity there).
$endgroup$
Usually the definition of a flow implies that the net flow on any vertex is $0$ except for the source or sink. Then, if you compute a maximum flow through your graph, you can force that either the flow on $(u, v)$ or the flow on $(v, u)$ is $0$. Then, if I understood correctly, what you are looking for is simply the flow on a path (i.e. the minimum value of the flow along the edges of this path). It might also be interesting for you to know that if all the capacities are integer, the maximum flow can be decomposed in paths of unit flows (i.e. full paths from source to sink, each one representing one car, although there will not be unicity there).
answered Nov 16 '12 at 10:19
beaubybeauby
74338
74338
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f238127%2findividual-components-of-flow-along-edges-in-a-graph%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