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 learnThroughout 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 use

drawing appropriate network(s)

carrying out an analysis using an algorithmic approach

drawing 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 cycles

  • connectedness

  • directed and undirected edges and graphs

  • You should:

  • be able to store graphs as matrices e.g. adjacency/distance matrices

  • understand 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 foundcommenting 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 path
  • commenting 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 verticesproblems 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 algorithmconverting a practical problem into the classical problem
    be able to determine lower boundsfinding 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 best
    • commenting 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 timesusing forward and reverse passes
    be able to identify critical activities and find a critical paththe 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 computersThe 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.