Decision 1 Maths Revision Notes plus Key Definitions

Decision 1 Maths Revision Notes plus Key Definitions

HideShow resource information
Preview of Decision 1 Maths Revision Notes plus Key Definitions

First 331 words of the document:

D1 Revision
Prim's, Kruskal's and Dijkstra's Algorithm
Prim's Algorithm: Choose any vertex to start the tree, selecting an arc of least
weight that connects from a node currently in the tree, to a node not currently
in the tree.
Kruskal's Algorithm: Sort the arcs in to ascending order of weight, using the
arc of least weight to start the tree, adding arcs in order of ascending weight,
rejecting those that form cycles.
Prim's on a Matrix: Choose any vertex to start the tree, number the column of
the chosen vertex and delete that vertex's row. Circle the lowest undeleted
entry in that column which becomes the next vertex.
Dijkstra's Algorithm: The start vertex is given final value zero. Each vertex
directly connected to that vertex is a given a working value:
Final value of previous vertex + weight of arc
The smallest working value is chosen. This becomes that vertex's final value.
This is repeated until the final vertex has a final value.
The route is found where: final label B ­ final label A = weight of arc AB
Graphs and Networks
Graph: A series of vertices connected by lines
Weighted Graph/Network: A graph where a number is associated with each
Subgraph: A subgraph of G is, a graph whose vertices and edges belong to G ­
part of the original graph
Degree/Valency: The number of edges incident to a vertex
Path: A finite sequence of edges such that the end vertex of one edge is the
start vertex of another and no vertex appears more than once
Walk: A path where you can return to vertices more than once
Cycle: A closed path
Digraph: A graph where edges have direction associated with them
Tree: A connected graph with no cycles

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

Spanning Tree: A subgraph of G, which includes all the vertices of G and is
also a tree
Minimum Spanning Tree: A tree such that the total length of its arcs is as
small as possible
Isomorphic Graph: A graph, which shows the same information but is drawn
Bubble Sort: If they are in order, leave them, if not, swap them. Stop when a
pass is completed with no swaps.…read more

Page 3

Preview of page 3

Here's a taster:

Route Inspection
Eulerian Graph: A graph where all the valencies are even
Semi-Eulerian Graph: A graph where precisely two vertices have an odd
valency and the rest are even (the two vertices with the odd valencies will be
the start and end point)
Traversable: A graph is traversable if you can travel along each arc once
without taking your pen off the paper
If there are more than two odd vertices, consider all possible pairings, choose
the smallest one and add it to the matrix.…read more

Page 4

Preview of page 4

Here's a taster:

For a Gantt chart, the critical path and each individual activity must have one
row each with floats drawn on the end
For a Scheduling Diagram, you must use the minimum number of rows to plot
all of the activities, shading in any slack time, DO NOT DRAW FLOAT
Lower bound for No. Of workers = Total Time of all activities/ Critical Path
Linear Programming
To formulate a linear programming problem you must:
1. Define the variables
2. State the objective
3.…read more


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »