vertices or nodes Adjacency matrix shows the routes from one vertex to another Kruskal’s algorithm: Prim’s algorithm:
/ edges Sum of leading diagonal = number of routes 1. Select the smallest 1. Choose any v
0 2 2 edge 2. Select smalle
Vertices are adjacent if A = 2 0 1 , A shows the number of 1 step routes vertex until a
2. Keep choosing
they share an edge 2 1 0 smallest edges until
8 2 2
Edges are adjacent if they 2
𝐴 = 2 5 4 , number of 2 step routes all are connected If weighted adjace
share a vertex 2 4 5 3. Find sum 1. Choose colum
row
Eulerian trail – visits every edge exactly once 𝑓𝑟𝑜𝑚 Minimum spanning trees 2. Smallest valu
Eulerian circuit – Eulerian trail that starts and ends on the same vertex A B (MST): column and n
Hamiltonian path – visits every vertex exactly once A 0 1 Found using Kruskal’s and 3. Delete row a
to B 2
Hamiltonian cycle – Hamiltonian path that starts and ends at the same 3 Prim’s solution
vertex From A to B = 1 4. Repeat until
been selecte
Chinese Postman Problem:
Wants to visit all edges at least once in the shortest time
No odd vertices:
Add up total weight of all edges
𝚐𝚛𝚊𝚙𝚑 Travelling Salesman Problem:
Requires a visit to all vertices exactly
Lower bound:
Two odd vertices:
Join them using the shortest route so they become even
𝑡𝑜𝑡𝑎𝑙 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑟𝑜𝑢𝑡𝑒 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜𝑑𝑑 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠
𝚝𝚑𝚎𝚘𝚛𝚢 1. Choose a random vertex
2. Find the sum of the two smallest
edges connected to this vertex
4 odd vertices: → Doing this with each of the vertic
Identify them and their possible pairs Deleted vertex algorithm: an increased lower bound
Choose the pairs with the least weight 1. Remove each vertex in turn or the Upper bound: (found using nearest n
𝑡𝑜𝑡𝑎𝑙 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤𝑒𝑖𝑔ℎ𝑡𝑠 𝑜𝑓 𝑟𝑜𝑢𝑡𝑒𝑠 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜𝑑𝑑 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 one the question directs you to algorithm)
If the postman wants to start in one place and end at remove 1. Start point in the current vertex
another: 2. Find the residual MST 2. Move to the nearest unvisited ve
Leave two odd vertices unconnected add the ‘cost’ of reconnecting the current vertex
Repeat the shortest pair of odd vertices, starting and deleted vertex (two shortest edges) 3. Repeat until all vertices have bee
ending with the longest pair 4. Return to the start vertex and fin
/ edges Sum of leading diagonal = number of routes 1. Select the smallest 1. Choose any v
0 2 2 edge 2. Select smalle
Vertices are adjacent if A = 2 0 1 , A shows the number of 1 step routes vertex until a
2. Keep choosing
they share an edge 2 1 0 smallest edges until
8 2 2
Edges are adjacent if they 2
𝐴 = 2 5 4 , number of 2 step routes all are connected If weighted adjace
share a vertex 2 4 5 3. Find sum 1. Choose colum
row
Eulerian trail – visits every edge exactly once 𝑓𝑟𝑜𝑚 Minimum spanning trees 2. Smallest valu
Eulerian circuit – Eulerian trail that starts and ends on the same vertex A B (MST): column and n
Hamiltonian path – visits every vertex exactly once A 0 1 Found using Kruskal’s and 3. Delete row a
to B 2
Hamiltonian cycle – Hamiltonian path that starts and ends at the same 3 Prim’s solution
vertex From A to B = 1 4. Repeat until
been selecte
Chinese Postman Problem:
Wants to visit all edges at least once in the shortest time
No odd vertices:
Add up total weight of all edges
𝚐𝚛𝚊𝚙𝚑 Travelling Salesman Problem:
Requires a visit to all vertices exactly
Lower bound:
Two odd vertices:
Join them using the shortest route so they become even
𝑡𝑜𝑡𝑎𝑙 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑟𝑜𝑢𝑡𝑒 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜𝑑𝑑 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠
𝚝𝚑𝚎𝚘𝚛𝚢 1. Choose a random vertex
2. Find the sum of the two smallest
edges connected to this vertex
4 odd vertices: → Doing this with each of the vertic
Identify them and their possible pairs Deleted vertex algorithm: an increased lower bound
Choose the pairs with the least weight 1. Remove each vertex in turn or the Upper bound: (found using nearest n
𝑡𝑜𝑡𝑎𝑙 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤𝑒𝑖𝑔ℎ𝑡𝑠 𝑜𝑓 𝑟𝑜𝑢𝑡𝑒𝑠 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑜𝑑𝑑 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 one the question directs you to algorithm)
If the postman wants to start in one place and end at remove 1. Start point in the current vertex
another: 2. Find the residual MST 2. Move to the nearest unvisited ve
Leave two odd vertices unconnected add the ‘cost’ of reconnecting the current vertex
Repeat the shortest pair of odd vertices, starting and deleted vertex (two shortest edges) 3. Repeat until all vertices have bee
ending with the longest pair 4. Return to the start vertex and fin
