How To Do Certain Questions

Question 1

How to show flow out of a node can’t be saturated

Answer 1

Compare flow in to flow out

Question 2

How to prove a flow shown is maximal

Answer 2

• 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

Question 3

Explain in max flow min cut

Answer 3

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

Question 4

How to show the complexity and determine it

Answer 4

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

Question 5

How to show the range for a CONSTSNT when comparing

Answer 5

Don’t lack, must compare to both things, and then show hence

Question 6

How to figure out puzzle work out the three question marks, how should you go about doing this

Answer 6

The evidence they gave, must use it IN ORDER
- move on to next only if done first
- this makes the justification better

Question 7

How to shoe how each constrain is reflorumated

Answer 7

Show before and arrow and after
DOMT have to define variables

Also for artifice say let Q = A1, and then arrow

Question 8

How to find the min completion time when reduce the workers

Answer 8

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 !

Question 9

How to find number of workers

Answer 9

Trial and error
1)all thr critical, there will be hints as you try
2) then try fit the gaps in.

Question 10

How to explain maximsie minimise

Answer 10

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

Question 11

How to group all thr constraints instsad of saying first 4

Answer 11

Say all of the STOCK constraints must now be

Question 12

How to find smallest dostance via d

Answer 12

Start dijkstra from d , and add the distance from g to d and then d to j

Question 13

How to answer why indepenent float 2 marks

Answer 13

Diesn’t affect overall priect

Or before or after

Question 14

How to show the minimise

Answer 14

Show adding of bith artificwl

Question 15

How to find the ranges , always use what

Answer 15

Use who,e part of question so use thr GRAPH TOO

Question 16

HOW TO DO 3 VARIABLE TO 2 VARIABLE LP

Answer 16

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

Question 17

How to do the minise instead

Answer 17

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

Question 18

How to reformualte properly , including combination

Answer 18

When doing the combination , skip out the INDIVIDUAL ones, they won’t make a difference but just long, not needed

Question 19

Why does every graph have even sum order?

Answer 19

Because every arc has two ends , hence for Esch arc the overall order will be 2 so overall it’s even

Question 20

How to say CONSTSNT for flow in flow out

Answer 20

• say flow in = flow out
• and only flow ins are xyz arcs and out are etc

EXPLAIN FULLY

Question 21

How to do ILP

Answer 21

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

Question 22

How to work out longest path

Answer 22

Write down the paths they gave, and try make a route out of it, using the fact can only go through one fsct

Question 23

To explain constraints for going in and out

Answer 23

= 1 say both don’t come or one goes in and one out that’s it

Etc

Question 24

How to prove root

Answer 24

Do 3 dp and SHOW CHANGE IF SIGN !:

Question 25

When reformualting with an equation, what to remember to do

Answer 25

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!

Question 26

Hiw to explain why maximum flow going out is equivalent to smaller

Answer 26

Say maixmise involves this

But because all the flow firm this arc goes thriughj this , then it is equivalent to say that

Question 27

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

Question 28

How to modify prims so certain arcs shown

Answer 28

Make them to smallest

Question 29

Prove complexities

Answer 29

Need the number of passes, normally n-1 you can check

Then just do 1 + 2 +3 … n-1
And show

Question 30

If I reduce a critical activity, is guaranteed it will lower by same amount

Answer 30

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

Question 31

Remember what does a critical activity mean in terms of the overall path

Answer 31

This means in overall path it must go from source to sink

Question 32

2 ways of proving activity can’t be completed in a minimum workers?

Answer 32

Divide the total durstion by length of one worker

Or show they overlapping

Question 33

OH FLIP, if they gave a maximise flow, and used extra pipes, then how could you find the maximum flow

Answer 33

Use these pipes, make a cut on these nodes and it should work

Question 34

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

Answer 34

Csn’t form a graoh let alone a tree, need atleast 8 arcs

Question 35

Which arc shall I increase capacitor of?

Answer 35

Only the arc which IS ALREADY STAUTURED, and increase it to the max capatoy ahead of