Loading…
Loading…
IB Applications and interpretation · SL and HL
Practise graph theory with step-by-step help. Free account.
| Term | Meaning |
|---|---|
| degree | the number of edges at a vertex |
| walk | a sequence of edges, vertices may repeat |
| Eulerian circuit | uses every edge once, ends where it starts: every degree even |
| Eulerian trail | uses every edge once: exactly two odd vertices, the ends |
| spanning tree | connects every vertex, no cycles, edges |
Handshake lemma
e.g.
Walks
Chinese postman
📖 Worked example
Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the weighted graph shown.
Kruskal: take the lightest edge each time that doesn't make a cycle
Try one like these, checked as you answer, with hints if you need them. Free, no sign-up.
| Name | Means |
|---|---|
| Hamiltonian path | visits every vertex exactly once |
| Hamiltonian cycle | a Hamiltonian path that returns to its start |
| travelling salesman problem | the shortest Hamiltonian cycle (on a table of least distances) |
| Bound | Algorithm |
|---|---|
| upper | nearest neighbour: go to the nearest unvisited vertex, then back to the start |
| lower | deleted vertex: a minimum spanning tree of the rest the two shortest edges from the deleted vertex |
📖 Worked example
The table shows the least distances, in km, between 5 towns: Use the nearest neighbour algorithm, starting at E, to find an upper bound for the travelling salesman problem.
Nearest neighbour: each time go to the nearest town not yet visited, then back to the start
📖 Worked example
The table shows the least distances, in km, between 6 towns: By deleting vertex B, find a lower bound for the travelling salesman problem.
Delete B: a minimum spanning tree of the other towns (Kruskal)
Try one like these, checked as you answer, with hints if you need them. Free, no sign-up.
Free account
Everything on this page stays free. An account is where graph theory practice starts adding up.
| Browsing | Account | |
|---|---|---|
| Read the notes and print worksheets and papers | ✓ | ✓ |
| Try a question with marking, hints and the step guide | ✓ | ✓ |
| Endless questions on every chapter, at every level | – | ✓ |
| Levels that unlock as you improve | – | ✓ |
| Your mistakes tracked by type, so you see what keeps costing marks | – | ✓ |
| WA practice papers on the chapters being tested | – | ✓ |
| Revision reminders before a topic fades | – | ✓ |
| Progress page and leaderboards | – | ✓ |