The graph below is used for problems 10, 11 and 12. A 31 В 40 20 22 21 35 26 33 -23 D 25 28 38 37 42. E 34 F 10. A mathematician applies the Greedy Algorithm to find the weight of the Hamiltonian circuit formed starting at vertex A. The order of the edges picked so far is AC, AF, BD, and CD. The next edge selected when applying the Greedy Algorithm should be a) DE b) BF c) EF d) none of these 11. The total weight of the circuit ABDFEA is a) 162 b) 147 c) 172 d) none of these 12. Using the Greedy Algorithm to find an approximate solution to the traveling salesman problem for a circuit starting at vertex D, the first edge to be selected should be а) BD b) AC c) AD d) none of these

The graph below is used for problems 10, 11 and 12. A 31 В 40 20 22 21 35 26 33 -23 D 25 28 38 37 42. E 34 F 10. A mathematician applies the Greedy Algorithm to find the weight of the Hamiltonian circuit formed starting at vertex A. The order of the edges picked so far is AC, AF, BD, and CD. The next edge selected when applying the Greedy Algorithm should be a) DE b) BF c) EF d) none of these 11. The total weight of the circuit ABDFEA is a) 162 b) 147 c) 172 d) none of these 12. Using the Greedy Algorithm to find an approximate solution to the traveling salesman problem for a circuit starting at vertex D, the first edge to be selected should be а) BD b) AC c) AD d) none of these

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Similar questions

Find the nearest neighbor algorithm to find a Hamilton circuit that begins at the vertex B.
18. ILL THUMBS UP
a. Given the following algorithm, def Linear Search(a, x): for i in range(0, len(a)): if a[i] == x: return i return -1 What will be the result if a = [1,2,5,3] and x = = 2? b. What will be the result if a = [1,4,2,0] and x = 10?
Find the LCM of the following using Euclidean Algorithm. 1. [48,32] 2. [35,50] 3. [75, 325] 4. [252,182] 5. [36, 64, 112] 6. [9a + 8,6a + 5]
B 15 D 12 A Use the Brute-Force Algorithm to find the lowest-cost Hamilton circuit. For the first part, give one best answer as a list of vertices visited starting at A (example: ABCDA), and for the second part give the total cost for this best solution. 1. Give a lowest-cost Hamilton circuit: 2. Give the lowest cost:
AE A B 40 D A E 25122 F C 35 30 B 40 20 £858:8 C 35 30 45 54 60 15 44 29 D 145 54 -- 34 11 E 22 60 15 34 50 F 24215 20 44 29 11 50 The weights of edges in a graph are shown in the table above. Apply the nearest neighbor algorithm to the graph starting at vertex A. Give your answer as a list of vertices, starting and ending at vertex A. Example: ABCDEFA
10. For the question use Nearest neighbor Algorithm. starting at vertices E, F, G and H. Give the circuit and the weight. Also, find the minimum Hamilton circuit from the table starting at G. E 10 10 10
QUESTION 2 Part 1: Use the graph shown to the right and the nearest- neighbor algorithm to find a Hamilton circuit that begins at vertex C 14 Be PD The weight of the circuit is 10 Part 2: 4 11 Use the best edge algorithm to find a Hamilton circuit. List the circuit beginning at vertex E. 7.
9. For the question use Fluery's Algorithm. Go to the slide 18 -21 in the PowerPoint of the Sec 14.2 and follow similar steps with at least 4 figures to find your Euler Circuit. Start the Euler Circuit at B. E C. A
The table gives the weights of a weighted graph G on vertices U, V, W, X, Y, Z. All the edges appear in the table (so for instance VZ is not an edge in the graph). Edge Weight Edge Weight Edge Weight UX 1 UV 3 UW 5 VX 1 YZ 3 XY 6 WY 1 WX 4 XZ 8 VW 2 WZ 5 UZ 9 i. Use Dijkstra's algorithm to find a minimal path from U to Z. ii. We now consider an graph G' whose vertices and edges are the same as G, but which is not a weighted graph. Sketch a planar diagram of G'. iii. Is it possible to add a new edge to G' and maintain planarity? Justify your answer either with a planar diagram or a proof of non-planarity.
3. To defeat Electro, Spider-Man needs to connect all the pylons (vertices) in the graph below with his webbing to form an electric circuit, with the numbers representing the difficulty of making the connection. Show that the Nearest Neighbor algorithm will NOT work for Spidey for this given graph. Try at least two different starting points, one of which should be the top left corner. 3 11 3 12 5 2 9 14 1 8 7 10 9 0 13 16