How To Do Certain Questions Flashcards
How to show flow out of a node can’t be saturated
Compare flow in to flow out
How to prove a flow shown is maximal
- find a cut for it
- state max flow min cut theory
Ocr says if a flow is found = to a cut, then that vut is minimum cut and thus max flow
IT WINT BE POSSIBLE TO FIND A CUT ELSEWISE
Explain in max flow min cut
If a value fo any cut is = to any Feasible Flow , then that cut is minimal and thus flow is maximal
Here, you won’t be able to find any FEASIBLE flow that’s also equal to a cut unless it’s the minimal cut and max flow hence by theory
You can find hella feasible flows that ARENT = TO A CUT , so don’t lack
- hence must read the final part of the question. If it says find a feasible flow here, and it’s not the maximum, then you won’t be able to use cut method, and will just have to trial and error, but hopefully all questions are like this
How to show the complexity and determine it
1) first must state the worse case
2) Don’t have to show each pass and each comparisons, maybe first few and establish it
3) need whole seauence, go to last term in terms of n (n-1)
4) show the sum is this and thus complexity is that
How to show the range for a CONSTSNT when comparing
Don’t lack, must compare to both things, and then show hence
How to figure out puzzle work out the three question marks, how should you go about doing this
The evidence they gave, must use it IN ORDER
- move on to next only if done first
- this makes the justification better
How to shoe how each constrain is reflorumated
Show before and arrow and after
DOMT have to define variables
Also for artifice say let Q = A1, and then arrow
How to find the min completion time when reduce the workers
1) first identify the problem section, and write this down
2) now create as much space as possible in front moving the non critical activities away ,
3) now try move these forward to reduce workers
(Remember can only move forward if we started with earliest times)
4) finally once everything move forward as much as possible, now move critical activity
Anything you move critical activity by increases the time by that much !
How to find number of workers
Trial and error
1)all thr critical, there will be hints as you try
2) then try fit the gaps in.
How to explain maximsie minimise
Say this represents the TOTAL COST, as it’s calaucktdd by number of units x cost
And we want to make this AS LOW AS POSISBLE SO HENCE MINIMISE
How to group all thr constraints instsad of saying first 4
Say all of the STOCK constraints must now be
How to find smallest dostance via d
Start dijkstra from d , and add the distance from g to d and then d to j
How to answer why indepenent float 2 marks
Diesn’t affect overall priect
Or before or after
How to show the minimise
Show adding of bith artificwl
How to find the ranges , always use what
Use who,e part of question so use thr GRAPH TOO
HOW TO DO 3 VARIABLE TO 2 VARIABLE LP
1) remember that youoknly plot your inequality constraints not agumenred
Basically you can only do this if you have an equality . NEVER PLOT THE EQUAL ONE ,use it TO REARRANEG FOR THE OTHER
- now reformulate the whole thing , and plot those only
How to do the minise instead
Rememebr when you reformualte the P , keep it in P form ( without 0
Reformualte, get rid of the numbers, and if all minus say same thing as minimising this and then do it
How to reformualte properly , including combination
When doing the combination , skip out the INDIVIDUAL ones, they won’t make a difference but just long, not needed
Why does every graph have even sum order?
Because every arc has two ends , hence for Esch arc the overall order will be 2 so overall it’s even
How to say CONSTSNT for flow in flow out
- say flow in = flow out
- and only flow ins are xyz arcs and out are etc
EXPLAIN FULLY
How to do ILP
Find optimal point
Then try find as many points next to and abive as possible until smallest.
Now double check it lies ahead if line
But yeah rememebr the FR identified , it can be anywhere where NOT ON THE LINE
How to work out longest path
Write down the paths they gave, and try make a route out of it, using the fact can only go through one fsct
To explain constraints for going in and out
= 1 say both don’t come or one goes in and one out that’s it
Etc
How to prove root
Do 3 dp and SHOW CHANGE IF SIGN !:
When reformualting with an equation, what to remember to do
Must remember to refolumate for NON NEGATIVITY constraints
- so x and y will stay 0, but must Reformkurse for z giving you ONE MORE EQUATION!
Hiw to explain why maximum flow going out is equivalent to smaller
Say maixmise involves this
But because all the flow firm this arc goes thriughj this , then it is equivalent to say that
Min cut is less than equal to , so by max flow min cut theroemer the max flow is ewuakt it the min cut and therefore the max flow is 106
How to modify prims so certain arcs shown
Make them to smallest
Prove complexities
Need the number of passes, normally n-1 you can check
Then just do 1 + 2 +3 … n-1
And show
If I reduce a critical activity, is guaranteed it will lower by same amount
No it will only lower as long as it’s critical!
If no longer critical because other activity bigger that becomes critical and thus it depends on that
Therefore there is a max to hoe much it can be lowered and affect activity time
Remember what does a critical activity mean in terms of the overall path
This means in overall path it must go from source to sink
2 ways of proving activity can’t be completed in a minimum workers?
Divide the total durstion by length of one worker
Or show they overlapping
OH FLIP, if they gave a maximise flow, and used extra pipes, then how could you find the maximum flow
Use these pipes, make a cut on these nodes and it should work
Rememebr the result that the sum of order of the vertices = 2 x arcs
So if I have 15 +x as the sum of the orders, and 7 arcs, why can’t I form a true
Csn’t form a graoh let alone a tree, need atleast 8 arcs
Which arc shall I increase capacitor of?
Only the arc which IS ALREADY STAUTURED, and increase it to the max capatoy ahead of
