Tree/cycle algorithms: Eulerian, Hamiltonian, MST (Kruskal/Prim), Chinese postman, TSP practice questions.

A connected graph has exactly two vertices of odd degree and all others of even degree. State what this guarantees about the graph.

• It has an Eulerian circuit but no Eulerian trail
• It has an Eulerian trail but no Eulerian circuit
• It has a Hamiltonian cycle
• It has neither an Eulerian trail nor an Eulerian circuit

Answer: It has an Eulerian trail but no Eulerian circuit

A connected graph has an Eulerian circuit exactly when every vertex has even degree, and an Eulerian trail that is not a circuit exactly when it has two odd-degree vertices, which must be the start and end. So with two odd vertices a trail exists but no circuit; nothing is guaranteed about Hamiltonian cycles.

A complete graph K₆ has 6 vertices, each connected to every other vertex. Determine the degree of each vertex.

• 4
• 5
• 6
• 15

Answer: 5

In a complete graph Kₙ every vertex connects to the other n − 1 vertices, so each vertex in K₆ has degree 6 − 1 = 5. (The value 15 is the number of edges, a common mix-up.)

Kruskal's algorithm builds a minimum spanning tree by repeatedly adding edges. Describe how the next edge is chosen at each step.

• The cheapest remaining edge adjacent to the current tree
• The cheapest remaining edge overall not forming a cycle
• The most expensive edge that does not create a cycle
• Any edge leaving the last vertex added

Answer: The cheapest remaining edge overall not forming a cycle

Kruskal considers all edges globally in increasing weight order, adding an edge only if it does not form a cycle. Choosing the cheapest edge adjacent to the current tree describes Prim's algorithm instead.

The Chinese postman (route inspection) problem on a connected weighted graph asks the traveller to do what?

• Visit every vertex exactly once and return to the start with least weight
• Cover every edge at least once, returning to the start at least cost
• Find the shortest path between two given vertices
• Find a spanning tree of least total weight

Answer: Cover every edge at least once, returning to the start at least cost

The Chinese postman problem seeks a closed walk that covers every edge at least once for minimum total weight; visiting every vertex once describes the travelling salesman problem instead.

Prim's algorithm is applied starting from vertex A. Describe the rule for selecting each subsequent edge.

• Add the globally cheapest unused edge that avoids a cycle
• Add the cheapest edge from a tree vertex to a non-tree vertex
• Add the cheapest edge between two vertices already in the tree
• Add edges in the order the vertices are labelled

Answer: Add the cheapest edge from a tree vertex to a non-tree vertex

Prim's algorithm grows a single connected tree, always adding the least-weight edge that connects a new vertex to the existing tree; choosing globally cheapest edges describes Kruskal's algorithm.

A weighted complete graph on 5 vertices is used for a TSP. Determine how many distinct Hamiltonian cycles must be compared when solving it by the brute-force method (treating a cycle and its reverse as the same).

• 10
• 12
• 24
• 120

Answer: 12

For n vertices the number of distinct Hamiltonian cycles is (n − 1)!/2 = 4!/2 = 24/2 = 12.