# Subject content

This is an extract of the full specification, which you can download from this page.

## 3.6 FSMQ Decision Mathematics (9997)

### Decision Mathematics (9997)

 What you need to learn Throughout your work you need to develop a critical and questioning approach to your own use of decision mathematics diagrams and techniques and also learn how these can be used to draw conclusions and summarise findings. You will carry out work that involves you in:selecting appropriate data to usedrawing appropriate network(s)carrying out an analysis using an algorithmic approachdrawing conclusions and summarising findings.The key ideas that you will meet and some specific techniques that you need to be able to use are set out below. Using networks to model real world situations You should be able to represent a situation so that some of the relationships are clarified by the use of appropriate networks.In drawing networks you should consider and understand:terminology such as vertices, edges, edge weights, paths and cyclesconnectednessdirected and undirected edges and graphsYou should:be able to store graphs as matrices e.g. adjacency/distance matricesunderstand the degree of a vertex and be aware of odd and even vertices
Trees and spanning treesYou should understand that a tree is a connected graph with no cycles and that every connected graph contains at least one tree connecting all the vertices of the original graph.

 In your study of trees you should: This includes: understand the idea of a minimum connector (a spanning tree of minimum length) finding minimum connectors using Prim's and Kruskal's algorithms You will be expected to apply these algorithms in graphical and, for Prim's algorithms, also in tabular form understand when a situation requires a minimum spanning tree to be found commenting on the appropriateness of a solution in its context appreciate the relative advantages of Prim's and Kruskal's algorithms
Shortest PathsIn developing ideas about shortest paths you will need to appreciate that problems of finding paths of minimum time and cost can both be considered to be shortest path problems

 In developing ideas about shortest paths you should: This includes: be able to apply Dijkstra's algorithm using a labelling technique to identify the shortest pathcommenting on the appropriateness of a solution in its context
Route Inspection ProblemIn developing ideas about route inspection you will need to appreciate the connection with the classical problem of finding an Eulerian trail.

 In developing ideas about route inspection you should: This includes: understand the significance of odd vertices problems with 0, 2 or 4 odd vertices be able to apply the Chinese Postman algorithm commenting on the appropriateness of a solution in its context
Travelling Salesperson ProblemIn developing ideas about the Travelling Salesperson Problem you will need to appreciate the connection with the classical problem of finding a Hamiltonian cycle.

 In developing ideas about the Travelling Salesperson Problem you should: This includes: be able to determine upper bounds by using the nearest neighbour algorithm converting a practical problem into the classical problem be able to determine lower bounds finding the length of a minimum spanning tree for a network formed by deleting a given node and then adding the two shortest distances to the given node. appreciate when a solution is sufficiently good realising that a solution is not necessarily the bestcommenting on the appropriateness of a solution in its context
Critical Path AnalysisIn developing ideas about Critical Path Analysis you will need to understand both how to construct and how to interpret activity networks with vertices representing activities.

 In developing ideas about Critical Path Analysis you should: This includes: be able to find earliest and latest times using forward and reverse passes be able to identify critical activities and find a critical path the calculation of floats know how to construct and interpret cascade diagrams
 Mathematical modelling You should be able to apply mathematical modelling to situation relating to the topics covered in this module. You will need to interpret results in contexts.
 Using calculators and computers The use of a standard scientific calculator is sufficient for this unit. However, software for the construction of networks or for the carrying out of algorithms is available commercially.