Individual components of flow along edges in a graph












0












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



the graphthe node



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 ?










share|cite|improve this question











$endgroup$

















    0












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



    the graphthe node



    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 ?










    share|cite|improve this question











    $endgroup$















      0












      0








      0


      1



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



      the graphthe node



      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 ?










      share|cite|improve this question











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



      the graphthe node



      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






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 7 at 7:28









      Glorfindel

      3,41981830




      3,41981830










      asked Nov 15 '12 at 18:19









      MustafaMustafa

      14817




      14817






















          1 Answer
          1






          active

          oldest

          votes


















          1












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






          share|cite|improve this answer









          $endgroup$













            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
            });


            }
            });














            draft saved

            draft discarded


















            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









            1












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






            share|cite|improve this answer









            $endgroup$


















              1












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






              share|cite|improve this answer









              $endgroup$
















                1












                1








                1





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






                share|cite|improve this answer









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







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Nov 16 '12 at 10:19









                beaubybeauby

                74338




                74338






























                    draft saved

                    draft discarded




















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    1300-talet

                    1300-talet

                    Display a custom attribute below product name in the front-end Magento 1.9.3.8