Networks Help

[josh8747]

Hi i was wondering if someone could please explain cutting in regards to Q3 Networks Module on the 2007 VCAA Exam 2, the way my text book explains it is to find every possible cut then find their values to find the min cut. Is there an easier way?

Any help would be appreciated!

[skinny]

tell me im cheating but i looked up the assessment report which is basically the answer sheet. ive never seen a question like this before tho. but what they mean is with all the lines that have arrows going to the right, add up all the numbers on those lines. its should come to 43. thats the answer.

[lacoste]

I think its called 'maximum flow' or minimum cut or something. havnt learnt it fully in class yet, but im sure networks is hell to learn especially this time of year.

[plato]

Hi i was wondering if someone could please explain cutting in regards to Q3 Networks Module on the 2007 VCAA Exam 2, the way my text book explains it is to find every possible cut then find their values to find the min cut. Is there an easier way?

Any help would be appreciated!

tell me im cheating but i looked up the assessment report which is basically the answer sheet. ive never seen a question like this before tho. but what they mean is with all the lines that have arrows going to the right, add up all the numbers on those lines. its should come to 43. thats the answer.

A cut is a line that completely separates the West Terminal from the East Terminal. The dotted line in the question is just one possible cut. To find the value of any cut, add up the values of all the edges that have arrows going from the West side toward the East side. You must ignore all values where/if the arrows go in the opposite direction (from the East side of the cut to the West side).

It may help to colour in the entire area on the left side (West Terminal side) of the cut. Then you just add all the edges that have been cut and whose arrows move from the coloured side to the uncoloured side. Note that, depending on the way you may draw a cut, some arrows coming from the coloured side may appear to be vertical or even going backwards but all that will matter will be if they are heading out of the coloured area.

By trial and error, and a little thought, you could find a cut somewhere that has the least value of all posible cuts for a network. This then gives the minimum cut for the network and this becomes the maximum flow through from West terminal to East Terminal.