USE OF MATHS decision notes

A word document on Prims, Kruskals and The Travelling Salesperson
- step by step method

HideShow resource information
  • Created by: Holly
  • Created on: 10-10-12 08:43
Preview of USE OF MATHS decision notes

First 138 words of the document:

Prims Algorithm
Step 1
Choose a start vertex.
Step 2
Connect the start vertex to the nearest new vertex by adding the shortest
edge.
Step 3
From any vertex on the tree so far, add the shortest edge that connects a new
vertex.
Step 4
Repeat step 3 until all the vertices have been included.
Matrix
Step 1
Choose a start vertex. Highlight the column corresponding to that vertex and
delete the row.
Step 2
Look in all the columns that have been highlighted so far. Circle the smallest
undeleted entry and read off the vertex for the row.
Step 3
Highlight the column corresponding to this vertex then delete the row.
Step 4
Repeat steps 2 and 3 until all the rows have been deleted.

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

Kruskal's Algorithm
Step 1
List the edges in order of weight, smallest first.
Step 2
Choose the edge with the smallest weight
Step 3
From the remaining edges, choose the edge with the smallest weight, as long
as it does not form a cycle with the edges already chosen.
Step 4
Repeat step 3 until all the vertices have been included.…read more

Page 3

Preview of page 3

Here's a taster:

Travelling Salesperson
Real world problem: Visit all the towns (vertices) and get back to the start.
The solution must be a complete cycle.
Method
Upper Bound
Nearest Neighbour
# start at a vertex.
# go to the closest vertex you haven't been to yet.
# from the current vertex, go to the next closest vertex you haven't been to
yet.
# when you get to the last vertex, go back to the start vertex by the
shortest possible route.…read more

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »