Maths with Lemon

Walks, Trails, Paths, Eulerian Circuits / Trails, Hamiltonian Cycles / Paths

What you have to know:

  • Nothing!! Just start here.

Key Points

  • 1. Watch the video:

Kruskal's Algorithm (and Prim's Algorithm)

What you have to know:

  • You add the shortest edges without making cycles. The solution is complete once you have reached all the vertices.

Key Points

  • 1. Watch the video on Kruskal's algorithm:

  • 2. Prim's Algorithm – watch this video

  • 3. Prim's algorithm and adjacency table – watch this video

  • 4. Read these notes on Kruskal's and Prim's algorithms

Chinese Postman Problem

What you have to know:

  • The Chinese postman problem (CPP) is to find the walk of least weight that goes along every edge at least once.
  • In the CPP for a graph with two odd vertices, the shortest route between the two odd vertices is found and duplicated. The solution will then be an Eulerian circuit.

Key Points

  • 1. Watch the video:

Travelling Salesman Problem (TSP)

What you have to know:

  • Classical travelling salesman problem (TSP): find a Hamiltonian cycle of least weight in a weighted complete graph.
  • Practical TSP: find the route of least weight which visits all the vertices at least once and returns to the starting vertex.
  • A practical TSP should be converted to the classical problem by completing a table of least distances where necessary.
  • The nearest neighbour algorithm is used to find an upper bound for TSP.
  • The delete vertex algorithm is used to find a lower bound for TSP.

Key Points

  • 1. Watch the video:

Adjacency Matrices

What you have to know:

  • How to calculate powers of a matrix. (If not, check this lesson)
  • The elements of an adjacency matrix raised to the power \(n\) show the number of walks of length \(n\) from one vertex to another.

Key Points

  • 1. Watch the video:

IB Past Paper Problems

Select a topic and unit, then click the button below to get a new problem.

Press the button to start!