Recognise how graphs model problems and how suitable graphs are constructed
Key knowledgeRecognise how graphs model problems and how suitable graphs are constructed.
Build the idea
A graph model should explain what each vertex and edge represents and which features of the situation are ignored. An algorithm must then operate on that representation. A breadth-first search grows a distance-layered set, while a spanning tree retains connectedness with no redundant cycle.
Try the sample task
Five rooms A,B,C,D,E have corridors AB,AC,BD,CD,DE. Model the rooms and corridors. Find the smallest number of corridors needed to travel from A to E, and list a shortest route.
The full worksheet includes the worked solution and remaining task set.
What this activity covers
These tasks develop selected examples of the requirement. Further examples and the associated Area of Study content are needed for full course coverage.