Question 5# This question introduces the idea of using a travelling salesman algo- rithm to search for a Hamilton circuit in any simple graph. (a) Find a Hamilton circuit for the graph G in- dicated by the diagram at right. Do this by eye, without using any particular algo rithm. Answer by drawing heavy lines over each edge on your circuit. There are many correct answers. (b) TSP algorithms usually work on a complete V(G) = V(G) weighted graph. One way E(G*) { {u,v} : uveV(G), u #v} to transform G into such a graph G is as shown. wt({u, v}) length of shortest path in G from u to v (i) How many weight-1 edges has G*? (ii) How many weight-3 edges has G*? (iii) How many edges has G* in total? (c) Suppose the Nearest Neighbour algorithm were applied to G*. How could you tell from the reported tour weight whether a Hamilton circuit of G had been found? (a) When applying Nearest Neighbour to G*, there will be situations where the current vertex has more than one nearest neighbour. We could then just pick one of them at random, but for grading purposes it is better to have a rule. Please use this: If the current vertex u has two or more equally close' available neighbouring vertices choose the one with the lowest compass bearing relative to u. (The compass bearing of a vertex v relative to u is the angle made by the the line uv to line uy where y is an imaginary point directly above u, and angles are measured in a clockwise direction. For example vertex of G has bearing 150 relative to vertex O.) Starting at the vertex determined by the last digit of your ANU ID, apply the Nearest Neighbour algorithm to G*. Draw your circuit on the enlarged diagram below. If necessary, used curved lines for 'virtual edges' (i.e. edges of G* that are not odges of G) to avoid these edges passing through other vertices. Mark your start vertex. Tour weight 6 Question 5# This question introduces the idea of using a travelling salesman algo- rithm to search for a Hamilton circuit in any simple graph. (a) Find a Hamilton circuit for the graph G in- dicated by the diagram at right. Do this by eye, without using any particular algo rithm. Answer by drawing heavy lines over each edge on your circuit. There are many correct answers. (b) TSP algorithms usually work on a complete V(G) = V(G) weighted graph. One way E(G*) { {u,v} : uveV(G), u #v} to transform G into such a graph G is as shown. wt({u, v}) length of shortest path in G from u to v (i) How many weight-1 edges has G*? (ii) How many weight-3 edges has G*? (iii) How many edges has G* in total? (c) Suppose the Nearest Neighbour algorithm were applied to G*. How could you tell from the reported tour weight whether a Hamilton circuit of G had been found? (a) When applying Nearest Neighbour to G*, there will be situations where the current vertex has more than one nearest neighbour. We could then just pick one of them at random, but for grading purposes it is better to have a rule. Please use this: If the current vertex u has two or more equally close' available neighbouring vertices choose the one with the lowest compass bearing relative to u. (The compass bearing of a vertex v relative to u is the angle made by the the line uv to line uy where y is an imaginary point directly above u, and angles are measured in a clockwise direction. For example vertex of G has bearing 150 relative to vertex O.) Starting at the vertex determined by the last digit of your ANU ID, apply the Nearest Neighbour algorithm to G*. Draw your circuit on the enlarged diagram below. If necessary, used curved lines for 'virtual edges' (i.e. edges of G* that are not odges of G) to avoid these edges passing through other vertices. Mark your start vertex. Tour weight 6
