I am trying to do June 2014 R for D2 and Q5 is flow augmenting. I managed to get a max flow of 104 but the mark scheme says 102. I checked one of my paths and it leads to a back flow of 3 down a 10 capacity arc. However this leads to conservation of flow not being true anymore.
Does anyone know why this is and if I need to use the entire capacity of an arc for a back flow?
Why is my back flow not working D2? Watch
- Thread Starter
- 28-06-2016 16:28
(Original post by BinaryJava)
- 28-06-2016 16:54
I checked one of my paths and it leads to a back flow of 3 down a 10 capacity arc.
When doing flow augmenting I ignore the direction of the actual flow, and just look at the forward/backward arrows. Once you've got numbers on all of those (which you're mostly given already in this paper) you don't need to know what direction it's actually going in!
EDIT: I'll take a look at the exact question now and I'll post my solution if you've not got it by then.Last edited by TLDM; 28-06-2016 at 16:58.
- 28-06-2016 17:24
Edit: hit submit early, oops.
Here's my workings. It's really messy because I've not done this for a while - sorry! Yours will probably look nicer than this. But hopefully what you can see is that I've not used arrows on my arcs - that's because it's best to simply ignore them. The flow-augmenting paths don't require you to know what the direction actually is.
(however, when determining which arcs are saturated, it's important to look at direction since otherwise you can't tell the difference between a saturated arc, and an arc with no flow.)Last edited by TLDM; 28-06-2016 at 17:30.