Maths with Lemon
Graph Theory
What you have to know :
-
Nothing!!
Walks-Trails-Paths- Eulerian circuit-Eulerian trail-Hamiltonian cycle-Hamiltonian path
1. Watch this video
2. Read these notes
What you have to know :
-
You add the shortest edges without making cycles. The solution is once you reached all the vertices.
Kruskal's algorithm
1. Watch this video
2. Watch this presantation
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. The solution will be a Eulerian circuit.
What you have to know :
-
Classical Traveling salesman problem (TSP) is to find a Hamiltonian cycle of least weight in a weighted complete graph.
-
The practical TSP is to 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 completion of 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 an lower bound for TSP
What you have to know :
-
How to calculate the power of a matrix
(If not check this lesson)
-
The elements of an adjacency matrix to a power of n shows the number of n walks that I can make to go from vertex to vertex.