Network in Graph Theory · 5.1.5
Solving network problems
Pupils apply network concepts to real problems, such as finding the cheapest, shortest or fastest route between two points on a weighted network. They also compare different transportation networks, and compare a network diagram with an actual map, discussing the advantages and disadvantages of each type of representation.
The official learning standard (5.1.5)
“Solve problems involving networks. The following comparisons, including the advantages and disadvantages, need to be involved: (i) between various transportation networks (ii) between transportation networks and maps.
Optimal cost problems need to be involved. Cost including time, distance and expenses.”
What it means
Pupils apply network concepts to real problems, such as finding the cheapest, shortest or fastest route between two points on a weighted network. They also compare different transportation networks, and compare a network diagram with an actual map, discussing the advantages and disadvantages of each type of representation.
How it is examined
Paper 2 structured questions typically present a weighted network diagram and require pupils to calculate the minimum total cost, time or distance for a route between two points, by comparing all possible paths. Questions may also ask pupils to discuss advantages and disadvantages of a network compared to a map.
Worked example
The diagram shows a weighted network connecting towns A, B, C and D, where the weights represent travel cost in RM: A–B = 8, A–C = 5, B–C = 4, B–D = 6, C–D = 9. Find the minimum total cost to travel from A to D.
- List all possible routes from A to D: A–B–D, A–C–D, A–B–C–D, A–C–B–D.
- A–B–D: 8 + 6 = 14.
- A–C–D: 5 + 9 = 14.
- A–B–C–D: 8 + 4 + 9 = 21.
- A–C–B–D: 5 + 4 + 6 = 15.
- Compare all totals (14, 14, 21, 15): the minimum is RM14.
Source:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Frequently asked questions
How do I find the optimal route in a network problem?
List all possible routes connecting the start and end points, add up the weights, such as cost, time or distance, along each route, then choose the route with the smallest total. For a small network, comparing every complete route directly is a reliable method.
Why compare a network diagram with a real map?
A network diagram shows only connections and costs, ignoring exact geography, so it is simpler for analysing routes. A map shows true distances, shapes and directions, which is more useful for actual travel.
Comparing both helps evaluate which representation suits a given purpose better.
Can two different routes have the same minimum cost?
Yes. If two or more routes give the same lowest total cost, time or distance, both routes are equally correct optimal answers, and either one may be stated as the solution to the problem.