7 - Algorithms

Question 1

What is a “Eulerian circuit”?

Answer 1

A circuit which includes EVERY edge of the graph exactly ONCE

Question 2

What is a “Eulerian graph”?

Answer 2

A graph which has a Eulerian circuit

Question 3

What is a “Eulerian trail”?

Answer 3

A walk with uses each edge exactly once (also called a Semi-Eulerian)

Question 4

What is important to remember about Eulerian trails?

Answer 4

Starts at one of the odd vertices and ends at the other

Question 5

What is a “Hamiltonian cycle”?

Answer 5

Visits each vertex exactly once and returns to the starting vertex

Question 6

What is a “Hamiltonian graph”?

Answer 6

When a graph has a Hamiltonian cycle

Question 7

What is a “Hamiltonian path”?

Answer 7

A path where each vertex is visited exactly once

Question 8

What is Kruskal’s algorithm?

Answer 8

Kruskal’s Algorithm builds a minimum spanning tree by adding edges at a time

1. Sort all edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree.
   –> If the edge created a cycle, then reject this edge
3. Keep adding edges until we reach all vertices

Question 9

What is Prim’s algorithm?

Answer 9

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

1. Specify a starting vertex
2. 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.
3. Stop when all vertices have been connected

Question 10

What is the Chinese postman problem?

Answer 10

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

Question 11

How is the Chinese postman problem carried out if there are 2 odd vertices?

Answer 11

1. Identify the two vertices of odd degree
2. Find the shortest path between those two vertices
3. The edges in this shortest path need to be used twice, all other edges only once
4. 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)

Question 12

How is the Chinese postman problem carried out if there are 4 odd vertices?

Answer 12

1. Write down all possible pairing between the four odd vertices (should be 3)
2. For each pairing possibility, find the total of the shortest distances between the two vertices in a pair
3. Select the pairing which gives the smallest total. The corresponding edges need to be repeated.

Question 13

What is the Traveling salesman problem?

Answer 13

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

Question 14

How would you calculate the UPPER BOUND for the Traveling salesman problem?

Answer 14

Nearest Neighbor Algorithm:

1. pick a starting vertex
2. go to the closest vertex not yet visited
3. repeat until all vertices have been used
4. add the final edge to return to the starting vertex

Question 15

How would you calculate the LOWER BOUND for the Traveling salesman problem?

Answer 15

Deleted Vertex Algorithm:

1. remove one vertex and all associated edges
2. find the length of the minimum spanning tree for the remaining graph
3. add the two shortest edges that were originally connected to the removed vertex