# Graphs and Networks | Maths with Lemon

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


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


##### What you have to know:

- Nothing!! Just start here.

##### Key Points

- 1. Watch the video:
- 2. Read this presentation

#### 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:
- 2. Read this presentation

#### 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:
- 2. Read this presentation

#### 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!

How was this problem?