Other pages in this set

Page 2

Preview of page 2

Here's a taster:

KRUSKAL'S ALGORITHM
This is an algorithm for finding a minimum spanning tree, or
minimum connector.
This is a spanning tree such that the total length of its edges is
as small as possible.…read more

Page 3

Preview of page 3

Here's a taster:

MATRIX FORM OF PRIM'S ALGORITHM
A network may be described using a DISTANCE MATRIX
Step 1 Choose a starting vertex and delete all
elements in that vertex's row and arrow its
column
Step 2 Neglecting all deleted terms, scan all arrowed
columns for the lowest available element and
circle that element
Step 3 Delete the circled element's row and arrow its
column
Step 4 Repeat steps 2 and 3 until all rows deleted
Step 5 The spanning tree is formed by the circled
arcs
3…read more

Page 4

Preview of page 4

Here's a taster:

DIJKSTRA'S ALGORITHM
This is for finding the shortest path in a network.
Use the following type of box:
Vertex letter Order of Final values
selection
Working values
Step 1 Label the start vertex S with a permanent
label of 0
Step 2 Put a temporary label on each vertex that can
be reached directly from the vertex that has
just received a permanent label.…read more

Page 5

Preview of page 5

Here's a taster:

THE CHINESE POSTMAN PROBLEM
If the graph is Eulerian it is traversable.
If it has some odd vertices then some arcs will have to be
repeated. These repeats will be such that when added to the
graph it will make the odd vertices even! This new graph is now
Eulerian and therefore traversable. We need to find the
repeats that make the total distance of these repeats as small
as possible.…read more

Page 6

Preview of page 6

Here's a taster:

BUBBLE-SORT ALGORITHM
Assuming you are "bubbling" from right to left:
Step 1
Compare the last two numbers on the extreme right. If the
smaller number is on the right, swap the two numbers and
reorder the list, if not, leave them.
Step 2
Move one step back in the list (to the left) and compare the
two numbers. If the smaller is on the right swap the two
numbers and reorder the list, if not, leave them.…read more

Page 7

Preview of page 7

Here's a taster:

QUICK-SORT ALGORITHM
Step 1
Locate the pivot element (use the element at the mid-point)
Step 2
Split the list into two sub-lists.
Sublist L1 contains those numbers less than or equal to the
pivot and are written to the left of the pivot.
Sublist L2 contains those numbers greater than the pivot
element and are written to the right of the pivot.…read more

Page 8

Preview of page 8

Here's a taster:

THE MAXIMUM MATCHING ALGORITHM
This improves an existing matching, if possible, by first
establishing an alternating path between vertices not in the
current matching. The status of the edges are then changed to
produce an improved matching.…read more

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »