algorithms Flashcards
How does the Planarity algorithm work?
1) Turn the Hamiltonian cycle into a polygon with all vertices on the outside.
2) List all the edges in any order.
3) Choose any unlabeled edge and label it (I)
4) Look at any unlabeled edges that cross the one just labelled. If any of these edges cross each other, the graph is non-planar. If none of these edges cross, give them the opposite label to the edge just labelled.
5) If all edges are labelled, the graph is planar.
How does Kruskal’s algorithm work?
1) List all the edges into ascending order of weight.
2) Select the edge with least weight to start the tree.
3) Move to the next edge in the list. If it would form a cycle, reject it. If it doesn’t form a cycle, add it to the tree.
4) Continue until all vertices are connected.
How does Prim’s algorithm work?
1) Choose a vertex to start the tree.
2) Select the lowest weight edge that joins a vertex in the tree to a vertex not in the tree.
3) Repeat until all vertices are connected.
How does Dijkstra’s algorithm work?
1) Label the start vertex with final value 0.
2) Record a working value at every vertex that is directly connected to the vertex that has just received its final value.
3) Look at the working values at all vertices without final values. Select the smallest working value. This now becomes the final value for that vertex.
4) Repeat until the final vertex receives its final value.
How would you use a MST method to find an UB for the TSP?
1) Find a MST for the graph.
2) Multiply the weight of the MST by 2 to find the initial UB.
3) Find shortcuts to bypass some parts of the MST and reduce the weight.
How would you use a MST method to find a LB for the TSP?
1) Remove a vertex from the graph and find its RMST.
2) Reconnect the removed vertex to the graph with its two shortest edges and add this to the weight of the RMST.
3) Repeat these steps by removing different vertices.
How would you use the nearest neighbour algorithm to find an UB for the TSP?
1) Select a vertex as a starting point.
2) Go to the nearest vertex that hasn’t been visited from the vertex just visited.
3) Repeat until all vertices have been visited and return to the start vertex using the shortest route.
4) Use all vertices as starting points and select the one with the lowest weight as the UB.
