3
$\begingroup$

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

$sat=2.5+.5$
$sact=2.5+3+3$
$sbat=1+1+.5$

... for the paths, and...

$sats=2.5+0.5+2$
$sbacs=1+1+3+1$

... for the cycles?

Thanks,
Hristo

  • 0
    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.2011-04-04

1 Answers 1

3

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)

  • 0
    acba and abca are not cycles...?2011-04-04