# Numbers | Maths with Lemon

Source: https://mathswithlemon.io/aa-geometry-trigonometry-Graph%20Theory.html


#### Walks, trails, paths, Eulerian circuit, Eulerian trail, Hamiltonian cycle, Hamiltonian path


##### What you have to know:

- No prior knowledge is required for this section. All concepts are introduced from scratch.

##### Key Points

- 1. Watch the video introduction below.
- 2. Read this presentation for a summary of the definitions and examples.

#### Kruskal's algorithm


##### What you have to know:

- You should understand what vertices, edges and weights represent in a graph.
- You should know what a cycle is and how to recognise one in a network.
- No prior algorithm experience is required.

##### Key Points

- 1. Watch the video introduction to Kruskal's algorithm.
- 2. Watch this video on Prim's algorithm as an alternative to Kruskal.
- 3. Watch this video on Prim's algorithm using an adjacency table.
- 4. Read these notes on Kruskal's and Prim's algorithms for worked examples.

#### Chinese postman problem


##### What you have to know:

- You must know how to identify odd and even vertices in a graph.
- You should understand what Eulerian trails and Eulerian circuits are.
- Basic familiarity with weighted graphs is helpful.

##### Key Points

- 1. Watch the video explaining the Chinese postman problem.
- 2. Read this presentation for notes and worked examples of CPP.

#### Travelling salesman problem


##### What you have to know:

- You should understand the difference between a Hamiltonian path and a Hamiltonian cycle.
- You should be able to interpret a distance or adjacency matrix.
- You should be comfortable comparing and calculating total route weights.

##### Key Points

- 1. Watch the video introduction to the travelling salesman problem.
- 2. Read this presentation for formal definitions, upper and lower bounds, and examples.

#### Adjacency matrices


##### What you have to know:

- You must know how to multiply matrices.
- You should understand what each row and column represents in an adjacency matrix.
- You should know that powers of an adjacency matrix show the number of walks of a given length between vertices.

##### Key Points

- 1. Watch the video on adjacency matrices and powers of matrices.

### IB Past Paper Problems

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

Press the button to start!

How was this problem?