What is a “Eulerian circuit”?
A circuit which includes EVERY edge of the graph exactly ONCE
What is a “Eulerian graph”?
A graph which has a Eulerian circuit
What is a “Eulerian trail”?
A walk with uses each edge exactly once (also called a Semi-Eulerian)
What is important to remember about Eulerian trails?
Starts at one of the odd vertices and ends at the other
What is a “Hamiltonian cycle”?
Visits each vertex exactly once and returns to the starting vertex
What is a “Hamiltonian graph”?
When a graph has a Hamiltonian cycle
What is a “Hamiltonian path”?
A path where each vertex is visited exactly once
What is Kruskal’s algorithm?
Kruskal’s Algorithm builds a minimum spanning tree by adding edges at a time
- Sort all edges from low weight to high
- Take the edge with the lowest weight and add it to the spanning tree.
–> If the edge created a cycle, then reject this edge - Keep adding edges until we reach all vertices
What is Prim’s algorithm?
Kruskal’s algorithm may be difficult to implement on large graphs (tough to check for cycles), therefore we use Prim’s algorithm!
Prim’s algorithm builds up the tree by adding vertices one at a time
- Specify a starting vertex
- At each stage find the vertex (which has not yet been added) that has the shortest possible distance to any of the vertices that have already been added.
- Stop when all vertices have been connected
What is the Chinese postman problem?
The Chinese postman problem is to find the shortest path around the graph which uses each edge at least once and returns to the starting point.
–> IF the graph is Eulerian, the Eulerian cycle is a solution to the problem
How is the Chinese postman problem carried out if there are 2 odd vertices?
- Identify the two vertices of odd degree
- Find the shortest path between those two vertices
- The edges in this shortest path need to be used twice, all other edges only once
- The length of the route is the total weight of all the edges plus the length of the edges that are used twice (the shortest path from the previous step)
How is the Chinese postman problem carried out if there are 4 odd vertices?
- Write down all possible pairing between the four odd vertices (should be 3)
- For each pairing possibility, find the total of the shortest distances between the two vertices in a pair
- Select the pairing which gives the smallest total. The corresponding edges need to be repeated.
What is the Traveling salesman problem?
The travelling salesman problem is to find the shortest route around a graph which visits each vertex at least once and returns to the starting point.
–> This is difficult to do, so you must calculate an UPPER and LOWER bound
How would you calculate the UPPER BOUND for the Traveling salesman problem?
Nearest Neighbor Algorithm:
- pick a starting vertex
- go to the closest vertex not yet visited
- repeat until all vertices have been used
- add the final edge to return to the starting vertex
How would you calculate the LOWER BOUND for the Traveling salesman problem?
Deleted Vertex Algorithm:
- remove one vertex and all associated edges
- find the length of the minimum spanning tree for the remaining graph
- add the two shortest edges that were originally connected to the removed vertex
