A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Network Graphs

# FM Network Graphs

## 7.4 Using Crashing to Reduce Completion Time

Note: if you cannot remember how to determine the critical path of an activity network, revise notes for 7.3 Determine Critical Paths and Float Times.

### Crashing

• Crashing refers to the process of reducing the duration of one or more activity in a project and then recalculating the project duration.
• Crashing could represent anything that reduces the duration of an activity, such as hiring more staff, favourable weather, utilising more efficient methods, etc.
• Crashing an activity on the critical path will generally lower the project duration.
• Crashing an activity which is not on the critical path will not change the project duration.
Read More »7.4 Using Crashing to Reduce Completion Time

## 7.3 Determine Critical Paths and Float Times

Note: if you cannot remember how to apply forward and backward scanning, revise notes for 7.2 Forward and Backward Scanning.

### Float Times

• The float time for an activity is the difference between its latest start time (LST) and earliest start time (EST).
• This represents the amount of time the individual activity can be postponed without changing the duration of the project overall.

Example

Above is an activity network which has undergone forward and backward scanning to determine the EST and LST of each activity. The float times of each activity can be calculated from these values:

Read More »7.3 Determine Critical Paths and Float Times

## 7.2 Forward and Backward Scanning

Note: if you cannot remember how to construct and analyse an activity network, revise notes for 7.1 Activity Networks.

### Scheduling Problem

• It is a problem of determining the minimum completion time for a project given its events.

### Earliest Start Time (EST)

• The earliest possible time that an activity can start.
• The earliest finishing time of an activity = EST of an activity + Duration of an activity

### Forward Scanning

• Forward scanning is a methodical process for finding the earliest start time (EST) for each activity in an activity diagram. The process works as follows:
Read More »7.2 Forward and Backward Scanning

## 7.1 Activity Networks

### Precedence Tables

• A precedence table lists each activity required to complete a project and the activities which need to be completed immediately before the activity can be begin. These are arranged into 2 columns.
• In many cases a third column is added (in the middle), listing the estimated duration of each activity.

Example

 Activity Duration (mins) Predecessors Boil water (B) 10 – Prepare Sauce (P) 15 – Cook Pasta (C) 15 Boil water Mix Sauce and Pasta (M) 2 Prepare Sauce, Cook Pasta

## 5.2 Introduction to Dijkstra’s Algorithm

### Dijkstra’s Algorithm

• Dijkstra’s algorithm provides a methodical method for determining the shortest path between two vertices.
• Dijkstra’s algorithm works as follows:

1.  Construct a table consisting of a row of empty elements where each column corresponds to each vertex in the network except the starting vertex, and the first (and for now only) row corresponds to the starting vertex.

2.  In each element of the row, write the weight of the edge connecting the starting vertex to the vertex of the corresponding column. If there is no edge such edge for a vertex, place a cross in that element instead.

3.  Draw a square around the lowest weight in the row.

Read More »5.2 Introduction to Dijkstra’s Algorithm

## 5.1 Shortest Path by Inspection

### Shortest Path Problems

• In many cases it may be useful to determine the shortest path between two vertices of a graph. For example, for a graph representing the road network interconnecting several towns, we may want to find the fastest way of getting from one town to another.
• The shortest path between two vertices is the path with the least weight.
• The weight of a path is found by summing the weights of each edge making up that path.

### Shortest Path by Inspection

• Finding the shortest path via inspection involves a crude trial and error approach whereby multiple possible paths are tested until the shortest is found.
Read More »5.1 Shortest Path by Inspection

## 4.2 Methods for Solving Flow Problems

### Inspection

• In small flow networks, it may be possible to determine the maximum flow.
• Remember that flow networks show the capacity of each edge. The maximum flow for an edge is often limited by the capacity of other edges. For example, if a pipe capable of carrying 100L/h is attached to one only capable of 50L/h, the maximum flow through the 100L/h pipe will be limited to 50L/h.

Example

Read More »4.2 Methods for Solving Flow Problems

## 4.1 Introduction to Flow Problems

### Flow Problems and Capacity

• Many networks rely on the transport of fluids, people, objects or other quantities between different locations. Generally, the medium that is taken from one location to another (the pipe, road, etc.) is capable of transporting a certain number or amount per unit of time. This is known as the capacity.
• Flow problems involves analysing movement through networks made up of a number of vertices connected via edges each with their own capacity.
• In Further Maths, we will generally analyse flow problems involving digraphs.
Read More »4.1 Introduction to Flow Problems

## 3.3 Guide to Minimal Connector Problems

Note: if you cannot remember how to construct minimum spanning trees using Prim’s algorithm, revise notes for 3.2 Minimum Spanning Trees.

### Guide to Analysing Minimal Connector Problems

• Minimal connector problems are problems which require the use of a minimum spanning tree.
• Always use Prim’s algorithm unless otherwise stated as inspection is more error prone and generally slower.
• It is generally easier to select a starting node with a small amount of edges.
Read More »3.3 Guide to Minimal Connector Problems

## 3.2 Minimum Spanning Trees

Note: if you cannot remember what a spanning tree is, revise notes for 3.1 Trees and Spanning Trees.

### Minimum Spanning Trees

• Most connected graphs will have multiple spanning trees. In a weighted graph, one of these spanning trees will have the lowest weight (i.e. the sum of each edge’s weight is the least). This is known as a minimum spanning tree.
• Minimum spanning trees are commonly used for optimisation problems. For example, when transferring products between towns, it is advantageous to know the fastest way of doing so.

### By Inspection

Read More »3.2 Minimum Spanning Trees