Networks
Graph Theory
Graph theory lets you turn a real network into vertices and edges, then ask sharp questions about routes, connections and efficient structures using real algorithms.
Introduction
Take a network you use — bus routes, flight connections, or the paths between rooms in your school — and represent it as vertices and edges. Once it is a graph, real questions become answerable: is there a route that covers every connection exactly once (an Eulerian trail), and if not, what is the shortest way to patch the network so that there is (the Chinese postman problem)? Graph theory here is AI HL content (syllabus topics 3.14 to 3.16); if you are studying AI SL or an AA course, treat this as an extension beyond your normal syllabus rather than routine coursework.
Guiding Questions
- Represent a real network you care about (friends, flights, train lines) as vertices and edges. What does the graph look like?
- What can degree, paths and cycles tell you about your network?
- Is there an Eulerian or Hamiltonian route through your network? What would it mean in real life?
- Use an algorithm (nearest neighbour, Kruskal) on your network and judge how good its answer is.