Embedded Files
New terminology
New terminology
The methods in this standard are part of Discrete Mathematics, in particular Graph Theory. They are closely linked to the field of Operations Research. You may have come across networks before when looking at Euler's formula.
Nodes and Edges
Nodes and Edges
In a mathematical sense, a network represents a system of objects, and relationships between them. For this standard, networks are in context, and we use the context of towns or places connected by roads or tracks.
The nodes of a network are the towns or places, and the edges are the roads between them.
The map shows five cities in France: Rouen, Paris, Orléans, Tours and Le Mans. The next shows the cities and main roads as a network.
The nodes have been given single letters to make them easier to describe. Notice that the nodes are dots, and the edges are lines between them.
An edge can be described by the nodes it is between. The edge between Rouen and Paris is R-P (or P-R, the order doesn't matter).
A small region of France.
A network of major roads between cities near Paris.
It's possible that more than one edge could connect the same pair of nodes. These are called multiple edges. This might be because there are two roads between a pair of towns.
The degree of a node is the number of edges that end at that node. A node is even if the degree is an even number (and odd otherwise). Think about asking "How many ways I can leave this town?".
In network above, the degree of Le Mans (L) is 3; it is an odd node.
A path in a network is a list of edges joined together. For instance, the path from Le Mans to Orleans is L-T-O. A circuit is a path that starts and ends in the same place. For example, P-L-R-P is a circuit, which starts and ends at Paris.
A network is connected if there is a path from any node to any other.
Distance
Distance
A map usually contains more information than just the towns and which ones are connected by roads. There is also a distance between two towns.
In the same way, a network will have weights on the edges. Every edge gets a weight, and weights are always positive*.
The distances between the cities of the Paris map have been added. We try to write them in a position where it's clear which road these refer to. Some authors write them in the middle of each edge (e.g. MathsNZ).
Distances between towns can be given in a distance table. These used to be an important and useful part of road maps. A distance table for the Paris map is below. Notice that although you can drive from Le Mans to Orléans, the distance table does not show this driving distance. It only shows the length of a direct connection. There are as many numbers in the table as there are edges in the network.
Network with edge weights added (distance in km).
*Negative weight edges are possible, but make some network methods considerably more complicated. They don't describe our typical "roads" context, and we won't have them.
In assessments for this standard, you will not be given the network, just the distance table and usually a node diagram (without the edges).
Checkpoint
Checkpoint
For the France roads network:
- Give an example of a node.
- Give an example of an edge.
- What is the degree of the Paris node?
- What is the weight of the edge T-L?
- Describe two paths from Rouen to Tours.
- Describe a circuit of four edges.
Exercises
Exercises
Use a copy of the exercise sheet and draw each network, including the weight of each edge.
Exercise.pdfTasks
Tasks
100 Acre Wood / Sherwood Forest / The Shire
100 Acre Wood / Sherwood Forest / The Shire
The initial task is the same for each:
Task 1: Use the distance table (Resource B) and node diagram (Resource C) on the Task Resource sheet to draw the network, including distances.
100acre.pdfsherwood.pdfshire.pdfKey words: network, node, edge, degree, odd, even, path, circuit, connected, weight
Google Sites
Report abuse