Standard Networks – Concepts and analysis

This lesson comprises four (4) master classes focusing on:

• Network terminology
• Creating networks
• Minimum spanning trees
• Shortest paths
• Critical path
• Flow capacity

Content:

MS-N2.1

• Identify and use network terminology: vertices, edges, paths, the degree of a vertex, directed networks and weighted edges
• Solve problems involving network diagrams
  • recognise circumstances in which networks could be used, eg the cost of connecting various locations on a university campus with computer cables
  • given a map, draw a network to represent the map, eg travel times for the stages of a planned journey
  • draw a network diagram to represent information given in a table
  • investigate and solve practical problems, eg planning a garbage bin collection route

MS-N2.2

• Determine the minimum spanning tree of a given network with weighted edges
  • determine the minimum spanning tree by using Kruskal's or Prim's algorithms or by inspection
  • determine the definition of a tree and a minimum spanning tree for a given network
  • use minimum spanning trees to solve minimal connector problems, eg minimising the length of cable needed to provide power from a single power station to substations in several towns
• Find the shortest path from one place to another in a network with no more than 10 vertices
  • identify the shortest path on a network diagram
  • recognise a circumstance in which a shortest path is not necessarily the best path or contained in any minimum spanning tree

MS-N3

• Construct a network to represent the duration and interdependencies of activities that must be completed during a particular project, for example a student schedule, or preparing a meal
• Given activity charts, prepare network diagrams and use critical path analysis to determine the minimum time for a project to be completed
  • use forward and backward scanning to determine the earliest starting time (EST) and latest starting time (LST) for each activity in a project
  • understand why the EST for an activity could be zero, and in what circumstances it would be greater than zero
  • calculate float times of non-critical activities
  • understand what is meant by critical path
  • use ESTs and LSTs to locate the critical path(s) for the project
• Solve small-scale network flow problems, including the use of the ‘maximum-flow minimum-cut’ theorem, for example determining the maximum volume of oil that can flow through a network of pipes from an oil storage tank (the source) to a terminal (the sink)
  • convert information presented in a table into a network diagram
  • determine the flow capacity of a network and whether the flow is sufficient to meet the demand in various contexts