Chapter 4 More Networks: Network Flows (min Max Cuts Etc ) Flashcards
What are network flows all about?
Why we use them
Bsdicslly like before we were trying to find minimum length, or route for pipes, but while we can find this we dint know if in REAL life this could work
For example I found the shortest way through the network, but can they actually allow the REQUIRED volume of water through? Or can the shortest paths in a fire exit allow enough people to go without being trampled
So we hse network flows to model flow of something and see if it’s possible to still achieve
So what is a network flow
Network showing the flow of capacity from a source to a sink
So we introduce idea of flow, going from a SOURCE to a SINK (all flow goes out, all flow goes in), where the arc weights now represent MAXIMUM CAPACITY OF FLOW through the pipe
What’s difference between feasible flow diagram and capacity diagram
Can they be shown on same diagram?
Capacity diagram just shows max capacities in each ARC
However feasible flow diagram shows actual flow that works based on capacities and rules
These could be superimposed on Esch other with feasible circled for example
What are rules about feasibility?
Maximum flow in the WHOLE diagram is capped to what?
Flow going in MUST equal flow going out
2) check max flow going into sink, this means this value is capped at max flow that could potentially leave the system
From a route , how to find total flow (fesbdile disgeam)
And looking at capacity diagram hoe to find maximum flow through a route
1) check the LOWEST flow , this is the total flow that can possible go through
2) again check lowest flow as this is THE MAX that can go through even though at different places more can go through, its limited to this
Two conditions for a network flow to be feasible
Flow in = flow out
Each arc weight is under or = to capacity
How to show a network flow of paths is FEASIBLE - what tables to draw
1) draw a table of ARC flow vs capacity
2) then a table of flow in and flow out
For each letter
Basically for each path, add the number of flow to EACH ARC, shown with + signs
- prove feasible if none of these exceed capacity p
Then show that total flow in = flow out of the letters, again showing flow and how this comes from different paths using + signs
When it says SABT has flow 5, what flow does each arc have?
Each arc will thus have 5 FLOW EACH, SA, AB and BT all have 5 flow
How do we find the maximum flow that can go through a network then, is there an algorithm, (what do we use)
There is an algorithm, however we don’t learn it
Instead we use cuts and theory behind them
What is a CUT
What does it Separate into
a cut is a division thst cuts the pipes into TWO SETS, one with the SOURCE, and one with the SINK
How to find the VALUE OF A CUT importsnt
How to know if unsure if arc goes from source to sink
Make the cut with a DOTTED LINE
Then only consider the arcs going from the SOURCE TO THE SINK, and add the capacity of them !
Thus if go from sink to source = value is 0
If unsure if they go by looking, write sets out and see that way
Does a cut necessarily mean this flow is fesbdible?
No, it just shows capscity going out irregardless if rest if network
HOW TO EASILLY IDENTIFY IF ITS GOINF FROM SINK TO SOURCE
All the dotted line section , imagine all of that BECOMES THE SOURCE , thus if arrows pointing towards it now, then thats sink to source so DISREGAED IT!
Remember, might have to go AROUND a node to make the cut
Don’t be afraid
What is MAX FLOW MIN CUT THEROEM
1) what does it mean for finding max flow
2) what else does the cut tell you!!!!!
If you find all the cuts in the system possible, then the MINIMUM CUT , will equal to the MAXIMUM FLOW THROUGH THE SYSTEM
I’m this case, the arcs that are affected In the cut (going from source to sink) will all be SATURATED TOO
Also , if they then tell you find the MAX flow and a fesbdile flow to match the system how would you do
(How would you find the rest of the flow once found the saturated ones )
1) You would somehow need to find the MINIMUM cut for the max flow, either do all or they will help you
2) now you know the arcs that have been cut must be SATURATED
If these are saturated, then you can MAKE UP THE REMAINING VALUES , based on flow in = flow out
What are supersources and super sinks and why add them
Basically if you a few sources and a few sinks in a system, and want ro complete it, add a SUPERSOURCE /SINK which goes into all three sinks or out of all three sinks into a node , and this COMPLETES THE SYSTEM
How to add the CAPACITIES going into each sink or source for super sink/source?
Basically the capacity must MNIMUM BE the total capacity of the spearates sinks, but in reality it could be (basically it’s gonna be limited by the mini sinks anyways )
This you could put million
In General , you just want to add ALL THE CAPACITIES TOGETHER for each branch!
Summary, what to do for capscitsd of super sink and source
As a rule of thumb, just add them tkgether and ensure it’s the same
In reality can be diff
Remember in a flow network, what directions must arcs go? Is there a specific one?
Other than SINK AND SOURCE which by definition have directed arcs, none other have to have one
As finding all the cuts are long to find max flow,if they give you values of some cuts and you look at flows how can you find max
Basically when does a flow ever match a cut!
Basically if they give values of cuts, and you find out values of flows and manage to find a Flow that MATCHES THE VALUE OF A CUT , then this must be the MAX FLOW MIN CUT
Thus a flow only matches a cut if it’S MAX FLOW MIN CUT !!!
Again when does a flow ever match a cut
Only when it’s max flow min cut
Thus if you can identify a flow that matches known cuts , you can quickly identify the max flow min cur
REMEMBER FEASIBLE RULE
Feasible only if
CAPACITIES ARENT EXCEEDED
AND FKOW IN = FLOW OUT
Importsnt
How to determine the total possible number of cuts and why
You know that in any cut, there will be two subsets , S and T, and thus every other vertex will either be in S, or T
So each vertex has a choice to make , and thus there are two possibilities
They are also INDEPENDENT OF EACH OTHER , thus probability has no effect
= 2x2x2x2 = 16
Summary of finding total cuts and why
= 2 ^ number of nodes excluding S and T
1) each node has 2 choices, either S or T per cut
2) choices are independent of other nodes (so multiply)
How to do removing pipe questions
Always look at ALL the cuts that involve REMOVED PIPE, and subtract this from each calc
Now look at desired weigth and see which one falls under category and in context
Essentiall first step is to REMOVE it from each calculation first
