Maximum Flow, Cut method

[tcstudent]

Hi guys, i always seem to struggle with finding the maximum flow for a directed graph, for instance their is a method of using minimum cuts by making cuts to firstly the Source and Sink, then making all other random cuts which i dont really understand either, furthermore my book that im using maths quest, its purple, well it has 2 lines explaining how to find the maximum flow through minimum cut method, worst explanation ever and therefore i dont understand how to do these questions.

if someone could please help me it would be wonderful, cheers.

[Cort]

Haha! This is also something I rather struggle with.

But I'll try explaining, see if it makes sense.

Just one thing to remember, because the further maths exam would use both terminology to confuse you (that's what I've experienced for the practice exams anyway).  1. Maximum flow = minimum cut.
2. The cut MUST separate SOURCE from SINK. If the cut just slaps the edges but it doesn't create a clear distinction between Source/Sink, then it would not work, nor will it be added.
3. Here's a bit hard to explain, so blame me if you don't get it: If the flow on one of the edges is against the flow from source to sink (eg: going from RIGHT to left), then it is not correct. If it's the simple version, it should be obvious as it flows backwards.
Or, how my teacher puts it:
If the source of the activity is LEFT of the cut, it is added.
If the source of activity is RIGHT of the cut, not added.

[brenden]

Moreover, if one activity is on The cut but can only be reached by something that has already been cut, you done count it be a use you can't get there.

[tcstudent]

haha thanks for trying, but i guess i still dont get it because i may need pictures to show me this, haha im going to connect lectures tomoz so ill ask them. cheers for trying man.

[sjayne]

The way I do it is by shading what is from the source to the left of the cut and then if there are lines going into the shaded area they don't count.

[brenden]

Tc, if you still don't get it after the connect lecture, come back here and I'll draw it out or whatever and make sure you get it.

[Cort]

Tc, if you still don't get it after the connect lecture, come back here and I'll draw it out or whatever and make sure you get it.

Could you er, draw it now if you have the time? Heh.

[tcstudent]

thank you, Last night i decided to do a further maths exam and then pick out the question i could not complete and noted them and will go tomoz and ask them i hope, if there not too busy.

[plato]

Maybe an answer to a question about Q3 on the 2007 Exam 2 paper might help you.

See    Re: Networks Help