Number 12 Please

Give an example of a weighted complete graph for which the cheapest Hamiltonian cycle costs exist100, hut the vertex-greedy algorithm finds a Hamiltonian cycle that costs exist1,000. Using the previous problem as a starting point, explain why the vertex-greedy algorithm can he wrong by any given amount, depending on the graph. Notice that the result of the vertex-greedy algorithm depends on the starting vertex. One way to counteract this is to run the vertex-greedy algorithm starting at each vertex, and taking as our approximate solution the cheapest Hamiltonian cycle out of all those runs. (This multiplies our efforts by the number of vertices in the graph, but this increase is nothing compared to the increase in the brute force method of attack.) Try this new version on the graph shown in Figure 7-127. For the graph in Exercise 12, use the edge-greedy algorithm to find a cheap Hamiltonian cycle, and compare this result to your answer to that exercise. Let G_n denote the graph whose nodes are labeled with all 2^n binary sequences of length n, and which has an edge from a to b whenever sequences a and b differ in only one position. For example, G_2 has nodes {100, 01, 10, 11} and edges {[00, 01], [00, 10], [01, 11], [10, 11]. Show that G_2, G_3, and G_4 are Hamiltonian