Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 graph the 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|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.