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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How would I write the flow of the following graph as a linear combination of flows along s,t-paths and t,s-paths and cycles? The values of the edges in the graph represent the flow along that edge.

enter image description here

I'm not sure how to actually express flow in terms of a linear combination of a path/cycle. Would it be something like...


... for the paths, and...


... for the cycles?


share|cite|improve this question
I'm not sure what it is that you're trying to do. Here it looks like you are writing some paths and giving them the weight associated to each edge. What's the real goal? – David Kohler Apr 4 '11 at 15:50
The weights on the edges are the flows along those edges. I'm trying to figure out how to write the flow of the graph as a linear combination of the flows. – Hristo Apr 4 '11 at 15:53
up vote 2 down vote accepted

Each of the basic flows you're using should conserve flow at nodes other than s and t. For convenience, write e.g [acba] as a flow of 1 unit on the cycle $a \to b \to c \to a$, and [sat] as 1 unit on $s \to a \to t$. So you could end up with something like $\frac{3}{2} [sat] + 2 [acba] + [abta]$ (just for illustration; that's not the answer here)

share|cite|improve this answer
acba and abca are not cycles...? – Hristo Apr 4 '11 at 15:42

Your Answer


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.