Further graphs and networks
Section overview:
The PowerPoint below provides an overview of material in this topic, including explanations and examples - for the full experience, open in a new tab then download it. All exercise references are to the new specification Pearson textbook - you can access the digital version for free or buy your own for extra practice.
Written summary notes are also given below for quick revision of key points, plus a selection of exam-style questions (with solutions) to test your understanding.
Click here for topic PPTs or see below for topic videos...
Topic videos:
- Hamiltonian cycles [Video repeated from Y12: Graph theory]
- The planarity algorithm
- Floyd's algorithm - setting up initial tables
- Floyd's algorithm - carrying out iterations
- Floyd's algorithm - interpreting the results
- Hamiltonian cycles and the travelling salesperson problem (TSP)
- TSP - upper bound (minimum spanning tree)
Notes:
Section 1 Notes - Planarity and Floyd's algorithms
Section 2 Notes - The travelling salesperson problem
Section 3 Notes - Resourcing and scheduling
Summary questions:
Extra resources:
Use the videos below to support your understanding of the topic. The ones on the left are specific to the course, building up to demos of exam-style questions; the ones on the right are for your own amusement, although the alternative outlook may provide you with a deeper overall understanding and appreciation of the topic.
Extra fun! The travelling salesman problem is known as an NP-hard problem - find out what that means (and more) below...