AS Decision Maths - Algorithms

Kruskal

1. List the arcs in order of smallest to largest - I find it helpful to tick them off on the graph so  I can make sure that I include them all!

2. Add the first to arcs into the spanning tree automatically as 2 won't form a cycle!

3. Consider each of the arcs working down the list from smallest to biggest, adding arcs that won't form a cycle by using a ✓ or if it will make a cycle, use a ☓ - but make sure you don't cross the arcs letters or value out, just put the cross by the side.

4. Write STOP once you have included the correct number of arc (no. of vertices - 1) THIS IS VERY IMPORTANT! Don't forget it;)

5. Finally make sure you have read the question! List the arcs in order if you have been asked to. If you have been asked to find the minimum spanning tree use your calculator to add up the total.

Prim on a graph (but not Everdeen;)

1. Start from the given vertex.

2. Then join in the vertex nearest to the start (the one with the lowest value)

3. Repeat this step with any of the vertices you have joined in, adding a new one each time.

4. It might be helpful to write the order in which you added them in!

5. Stop when you have included all the vertices, once.

6. If you have any cycles you have gone wrong!

Prim and Kruskal should always turn out the same minimum spanning tree so you can check them against each other to make sure they're right! 

Prim on a matrix (Srill not Primrose Everdeen;)

1. Start from the given vertex.

2. Number that vertex's column 1. (Column is going down)

3. Then cross out the row - going across. e.g. Start at A, number A's column 1 then cross out the A row.

4. Circle the smallest value in any column with a number at the top.

5. List the arc(s) in the order you add them in.

6. You then number the new column e.g. the smallest number in column A was 7 and it was in row C, so column C now has a 2 above it and you cross out the row C but make sure you can see the circled number!

7. Repeat until all rows are deleted and all the colums have numbers above.

Route inspection urg...

1. List the order of each of the vertices (how many edges are going out of it)

2. Highlight/List all the odd vertices - there will be an even number of odd vertices!

3. Form all possible pairs of odd vertices e.g. odd vertices = A,B,C,D so the pairs could be: AB CD or AC BD  or AD BC

4. Now you need to find the value for going along each of the pairs of vertices. Sometimes you may have to go via another vertex if AB doesn't have a direct route; go AEB then add the weight of AE and EB together! Use the graph to help you and list all repeated arcs.

5. Do this for all the pairs of odd vertices and see which combination has the lowest value e.g AB CD = 110, AC BD = 230 and AD BC = 175. So AB CD has the lowest value.

6. You can now draw on the acrs you will go along twice or repeat!

7. You can now write down the order/route starting and ending at the same vertex - List it as a string of letters, making sure ever edge in covered and going down the repeated egdes.