Pages in this set

Page 1

Preview of page 1
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,…

Page 2

Preview of page 2
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


Page 3

Preview of page 3
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…

Page 4

Preview of page 4
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



No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »