Graph theory and network IA ideas (AI HL and beyond)

How networks & graphs explorations reach the top bands

Personal engagement (C)

Map a network you actually use (your school, your town's transport, your friends) and collect the distances or connections yourself.

Reflection (D)

Reflect on what the graph leaves out (one-way systems, time of day, capacity) and whether the algorithm's answer would work in practice.

Use of mathematics (E)

SL: Graph theory is in AI HL. At SL, keep to distance tables and simple optimisation, or explain any algorithm you use carefully as new mathematics.

HL: Correct use of HL algorithms (Kruskal/Prim, Chinese postman, nearest neighbour and deleted-vertex bounds, adjacency matrices, Markov steady states), with each step explained and the result interpreted.

An HL version

Compare two algorithms or bounds, work with the adjacency or transition matrix directly, or prove why an algorithm gives an optimal (or bounded) answer.

Networks, graphs & algorithms ideas (9)

• What is the shortest route to walk every corridor in my school?AI HLSolid
• What is the cheapest way to connect villages with fibre broadband?AI HLAI SLSolid
• Planning the shortest delivery round: bounds for the travelling salesman problemAI HLSolid
• How does Google rank pages? PageRank on a small websiteAI HLAA HLAmbitious
• How connected is my year group? Analysing a friendship networkAI HLAI SLSolid
• Which Underground station is the most central?AI HLAI SLSolid
• Will one phone brand take over? Brand loyalty as a Markov chainAI HLSolid
• How many flights does it take to get anywhere?AI HLAI SLAmbitious
• What is the fewest number of exam sessions my school needs?AI HLAA HLAI SLSolid

Also relevant (12)

• How fast does news spread through a year group?AI SLAI HLAA SLAA HLSolid
• Voronoi diagrams in a grid city: Euclidean or taxicab distance?AI SLAI HLAA HLAmbitious
• Which airport is really closest? Voronoi diagrams on a curved EarthAI SLAI HLAmbitious
• Should bigger hospitals get bigger regions? Weighted Voronoi diagramsAI HLAI SLAmbitious
• Why do flight paths curve on the map?AA SLAA HLAI SLAI HLAmbitious
• How does RSA encryption work, and how long would it take to break a small key?AA HLAA SLAmbitious
• How long does a game of Snakes and Ladders last?AI HLAA HLAmbitious
• Which Monopoly squares are landed on most often?AI HLAA HLAmbitious
• What are the chances of rolling a Yahtzee in one turn?AA SLAA HLAI SLAI HLSolid
• What are the odds in a Risk battle?AA SLAA HLAI SLAI HLSolid
• A fractal shortcut for the travelling salesman: ordering stops along a Hilbert curveAI HLAA HLAmbitious
• Balancing traffic flow through a road network with linear equationsAI HLAI SLAA HLSolid