A graph is made up of  vertices (points), edges (lines) and regions (faces.)  Drawing a planar graph connects vertices without edges crossing.

Planar

Non Planar

Loop
An edge that connect from an vertex to itself. A loop counts as one edge in the number of edges.

The Degree of a Vertex
The number of edges connected to a vertex.

A loop counts as two edges for the degree.

Vertices are classified as even or odd if their degree
is an even number or odd number.

An isolated vertex does not join to the graph.

A connected graph has no isolated vertices.

Handshaking Lemma
Every edge is counted by the degree of two vertices.
Sum of vertex degrees = 2 × number of edges.

Euler's Formula for Planar Graphs.

For any connected planar graph with  vertices,  edges and  faces, we have

A graph may look nonplanar but can be redrawn to be planar.

 

For a simple, connected, planar graph 𝑒 + 6 ≤ 3𝑣, provided there are at least 3 vertices
If a graph fails this test it cannot be planar.

 

Making a meal Note: The scenario used in this activity comes from NESA’s Mathematics Standard 2 Network Topic Guidance. The following tasks are required to make a curry for dinner for a family of 4:   A = Chop vegetables B = Mix spices C = Cook curry D = Cook papadums E = Place papadums and chutney on table F = Cook rice G = Put curry and rice on plates H = Put plates on table.

Acivity Immediate Predessor A - D - F - G F B A E D C B H G

 

Questions

The critical path:

• What is the shortest time you could take to make and serve the meal?

23 minutes

• How do you know this?

This is the longest path from the start to the finish.

• Which tasks lie on this path?

F, G and H.

• What would happen to the serving time of the meal if the rice took 24 minutes instead of 20 minutes?

The meal would be served 4 minutes late (it would be delayed by 4 minutes). The total time would rise from 23 to 27 minutes.

The critical path is the sequence of network activities which combine to have the longest overall duration so as to determine the shortest possible time needed to complete a project.

The length of the critical path is the critical time which gives the minimum time for completion of the project.

Each activity on the critical path is called a critical step.

• What will happen if a critical step is delayed?

If a critical step is delayed then the whole project is delayed by this amount of time.

Note: The sample answers have been made assuming the start time is time zero.

Earliest start time (EST):

• What is the earliest time you could start activity C?

6 minutes

• Explain how you know this.

The earliest time their prerequisites can be finished.

The earliest starting time is the earliest time that any activity can be started after all prior activities have been completed.

Latest start time (LST):

• What is the latest time you could start activity C without delaying the serving of the meal?

10 minutes

• Explain how you know this.

The latest time they could be started without delaying the meal. This is the time you need to start so that this activity and all subsequent activities can be completed in 23 minutes.

The latest starting time is the latest time an activity may be started after all prior activities have been completed and without delaying the project.

Float time:

• What is the maximum time you could delay activity C without delaying the meal?

4 minutes

• How could you use the LST and EST to calculate these?

LST – EST, the difference between them.

Float time is the amount of time that a task in a project network can be delayed without causing a delay to subsequent tasks.

• Is B, E or G on the critical path? G

• What can you conclude about the float time of tasks which lie on the critical path?

Their float times are zero. They cannot be delayed without delaying the project.

• What is the relationship between the LST and EST for tasks on the critical path?

The LST and EST are equal.