Determine the circuit of minimal length in the given graph.NEED STEPSSolution. We can chose any initial vertex, we start from A and we list all the possibilitieswith the corresponding lengths.Path LengthA, B, C, D, A 97A, B, D, C, A 108A, C, B, D, A 141A, C, D, B, A 108A, D, B, C, A 141A, D, C, B, A 97We could also have avoided the circuits in opposite directions.A shortest Hamilton circuit is A, B, C, D, A (or A, D, C, B, A) and it has length 97. 2. Determine the circuit of minimal length in the given graph.204234303512Solution. We can chose any initial vertex, we start from A and we list all the possibilitieswith the corresponding lengths.PathLength97А, В, С, D, AА, В, D, C, AА, С, В, D, AА, С, D, B, AА, D, B, C, AА, D, C, B, A10814110814197We could also have avoided the circuits in opposite directions.A shortest Hamilton circuit is A, B, C, D, A (or A, D, C, B, A) and it has length 97.

Consider the given graph. It has 4 vertices A, B, C and D. We have to determine a circuit of minimal length in the given graph. For this, we choose an initial vertex and find out all the possible Hamiltonian circuits from that vertex. Note that, a Hamiltonian circuit in a graph is a path that visits each vertex of the graph exactly once except for starting and ending at the same vertex.We choose the initial vertex as A. Note that, A is adjacent to 3 vertices, B, C and D. If we choose the next vertex in circuit as B, A-B has length 20. From A-B, if we choose the next vertex as C, the length of A-B-C is 20 + 30 = 50. From A-B-C, if we choose the next vertex as D, the length of A-B-C-D is 50 + 12 = 62. So, we visited all the 4 vertices of the given graph exactly once. Now, it remains to go back to the starting vertex A. From A-B-C-D back to A, we get the circuit A-B-C-D-A with length 62 + 35 = 97. Proceeding like this, if we choose the circuit A-B-D-C-A, this circuit have length 20 + 34 + 12 + 42 = 108. These are the only two circuits from A immediately followed by B. Next, we choose the second vertex after A as C. Proceeding like in the above cases, the circuit A-C-B-D-A has length 42 + 30 + 34 + 35 = 141. The another circuit that has C immediately after A is A-C-D-B-A with length 42 + 12 + 34 + 20 = 108. These are the only two circuits from A immediately followed by C. Next, we choose the second vertex after A as D. Proceeding like in the above cases, the circuit A-D-B-C-A has length 35 + 34 + 30 + 42 = 141. The another circuit that has D immediately after A is A-D-C-B-A with length 35 + 12 + 30 + 20 = 97. These are the only two circuits from A immediately followed by D.Thus we got a total of 6 circuits in the given graph starting from A. Path Length A,B,C,D,A 97 A,B,D,C,A 108 A,C,B,D,A 141 A,C,D,B,A 108 A,D,B,C,A 141 A,D,C,B,A 97 It can be noted that the circuits A,B,C,D,A and A,D,C,B,A represent the same circuit in opposite directions. Similarly, the circuits A,B,D,C,A and A,C,D,B,A represent the same circuit in opposite directions and the circuits A,C,B,D,A and A,D,B,C,A represent the same circuit in opposite directions. So, excluding these repetitions, we have only 3 circuits. They are A,B,C,D,A of length 97, A,B,D,C,A of length 108 and A,C,B,D,A of length 141. Thus, a shortest Hamiltonian circuit is A,B,C,D,A (same as A,D,C,B,A) and it has length 97.