onsider a graph of five vertices whose vertices are labelled 1 to 5. The only edges present in the graph are one each from 1 to 2, 1 to 3, 1 to 4 and 1 to 5. Let the time taken to travel from 1 to 2, 3, 4 and 5 be 5, 5, 1 and 1 units respectively. Also assume that if it takes time t to travel from vertex a to b, then it takes the same time to travel from b to a.We wish to select a walk from vertex 1 to some other vertex, back to vertex 1 and so on till each vertex (except vertex 1 - the source) is visited exactly once.
Let the initial instant be t = 0. Let the times of visit of vertices 2, 3, 4 and 5 from t = 0 be t2, t3, t4 and t5.We wish to minimise the sum of t2, t3, t4 and t5.
Find out the minimum possible sum of the given times.
To minimise the total time of visiting, we select the path which takes minimum time first because this time piles up on all other vertices. After we come back to 1,we then select the path with second minimum time and we repeat this process each time after we come back to 1.
Let the times in sorted order be a,b,c and d for vertices v1,v2,v3 and v4. Then vertex v1 is visited at time t = a.We come back to 1 at t = 2a.We then reach the second vertex at t = 2a + b and come back to 1 at t = 2a + 2b. Continuing similarly, vertex v3 is visited at t = 2a + 2b + c and v4 is visited at t = 2a + 2b + 2c + d. So, the minimum value of the sum of times would be 7a + 5b + 3c + d.
So, the answer is 32.