algorithm steps

Question 1

planarity algorithm:

Answer 1

find a hamiltonian cycle
make the hamiltonian cycle a polygon with other edges inside
list all the edges
choose one to label I for inner
if any cross, label them O for outer
if any edges cross each other still, it’s not planar
continue labelling O and I until all are labeled, then redraw as planar

Question 2

Kruskals:

Answer 2

Choose the smallest in order, no regard for connections, no cycles

Question 3

Prims:

Answer 3

Choose a vertex
Select the arc of least weight connected
Then consider all connected to that Too
Until all good and no cycles

Question 4

Dijkstras:

Answer 4

Letter in first box, order in second, length in last
Work out all connected to first vertex 
Find shortest
Work out all connected
Correct any that need it 
Find shortest overall
Repeat until done

Question 5

route inspection:

Answer 5

if all vertices are even, it’s just the total weight
find all odd vertices
work out distance between each pair - if that’s only one pair it’s chill
use the one with the shortest distance
add that distance to the total

Question 6

simplex (max):

Answer 6

find pivot column - most negative in objective function (bottom one)
find theta values - value/pivot column value
find row with the smallest positive theta value
divide that row by the intersection of the column and row (so gives 1 at intersection)
then make the other values in the pivot column 0 with row operations (so apply same to all values in row) and change row to pivot column (in name only)
repeat until all in objective function are positive
values are from rows not columns

Question 7

simplex (min):

Answer 7

Q=-P, maximising that
find pivot column - most negative in objective function (bottom one)
find theta values - value/pivot column value
find row with the smallest positive theta value
divide that row by the intersection of the column and row (so gives 1 at intersection)
then make the other values in the pivot column 0 with row operations (so apply same to all values in row) and change row to pivot column (in name only)
repeat until all in objective function are positive
Then return to P (all stays the same except Q/P)
values are from rows not columns

Question 8

simplex setup:

Answer 8

rearrange so all = value or 0
<= - minus surplus variable, =0 or 1 if it’s the row of itself
>= - minus surplus, +artificial which =integer on the other side

Question 9

simplex with >=:

Answer 9

do simplex twice - once until all positive in objective function and OF=0 (if not there’s no feasible solution) (sum of artificials will be 0 - in rows not columns), then normally without artificials

Question 10

big m method:

Answer 10

change objective function - -M*artificial at the end
rearrange so just value on one side
do as usual - M is always largest
then as these use artificial, do it again now artificial is gone