Chapter 4 More Networks: Network Flows (min Max Cuts Etc )

Question 1

What are network flows all about?

Why we use them

Answer 1

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

Question 2

So what is a network flow

Answer 2

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

Question 3

What’s difference between feasible flow diagram and capacity diagram
Can they be shown on same diagram?

Answer 3

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

Question 4

What are rules about feasibility?

Maximum flow in the WHOLE diagram is capped to what?

Answer 4

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

Question 5

From a route , how to find total flow (fesbdile disgeam)

And looking at capacity diagram hoe to find maximum flow through a route

Answer 5

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

Question 6

Two conditions for a network flow to be feasible

Answer 6

Flow in = flow out

Each arc weight is under or = to capacity

Question 7

How to show a network flow of paths is FEASIBLE - what tables to draw

Answer 7

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

Question 8

When it says SABT has flow 5, what flow does each arc have?

Answer 8

Each arc will thus have 5 FLOW EACH, SA, AB and BT all have 5 flow

Question 9

How do we find the maximum flow that can go through a network then, is there an algorithm, (what do we use)

Answer 9

There is an algorithm, however we don’t learn it

Instead we use cuts and theory behind them

Question 10

What is a CUT

What does it Separate into

Answer 10

a cut is a division thst cuts the pipes into TWO SETS, one with the SOURCE, and one with the SINK

Question 11

How to find the VALUE OF A CUT importsnt

How to know if unsure if arc goes from source to sink

Answer 11

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

Question 12

Does a cut necessarily mean this flow is fesbdible?

Answer 12

No, it just shows capscity going out irregardless if rest if network

Question 13

HOW TO EASILLY IDENTIFY IF ITS GOINF FROM SINK TO SOURCE

Answer 13

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!

Question 14

Remember, might have to go AROUND a node to make the cut

Answer 14

Don’t be afraid

Question 15

What is MAX FLOW MIN CUT THEROEM
1) what does it mean for finding max flow
2) what else does the cut tell you!!!!!

Answer 15

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

Question 16

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 )

Answer 16

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

Question 17

What are supersources and super sinks and why add them

Answer 17

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

Question 18

How to add the CAPACITIES going into each sink or source for super sink/source?

Answer 18

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!

Question 19

Summary, what to do for capscitsd of super sink and source

Answer 19

As a rule of thumb, just add them tkgether and ensure it’s the same

In reality can be diff

Question 20

Remember in a flow network, what directions must arcs go? Is there a specific one?

Answer 20

Other than SINK AND SOURCE which by definition have directed arcs, none other have to have one

Question 21

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!

Answer 21

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

Question 22

Again when does a flow ever match a cut

Answer 22

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

Question 23

REMEMBER FEASIBLE RULE

Answer 23

Feasible only if
CAPACITIES ARENT EXCEEDED

AND FKOW IN = FLOW OUT

Question 24

Importsnt

How to determine the total possible number of cuts and why

Answer 24

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

Question 25

Summary of finding total cuts and why

Answer 25

= 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)

Question 26

How to do removing pipe questions

Answer 26

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