TIFR CSE 2020 | Part B | Question: 14

Question

The figure below describes the network of streets in a city where Motabhai sells $\text{pakoras}$ from his cart. The number next to an edge is the time (in minutes) taken to traverse the corresponding street.

 

At present, the cart is required to start at point $s$ and, after visiting each street at least once, reach point $t$. For example, Motabhai can visit the streets in the following order $$s-a-c-s-e-c-d-a-b-d-f-e-d-b-t-f-d-t$$

in order to go from $s$ to $t$. Note that the streets $\{b,d\}$ and $\{d, f \}$ are both visited twice in this strategy. The total time taken for this trip is $440$ minutes [which is, $380$ (the sum of traversal times of all streets in the network) $+ 60$ (the sum of the traversal times of streets $\{b,d\}$ and $\{d,f\}$)].

Motabhai now wants the cart to return to $s$ at the end of the trip. So the previous strategy is not valid, and he must find a new strategy. How many minutes will Motabhai now take if he uses an optimal strategy?

Hint: $s, t, b$ and $f$ are the only odd degree nodes in the figure above.

• A. $430$
• B. $440$
• C. $460$
• D. $470$
• E. $480$

Comments

I solved it by option elimination, since 440 is the time taken to go from s to t,if he follows the same path in reverse he can do it in 440 minutes. so we are left with option a and option b. Next its mentioned previous strategy is not valid and a new optimal is to be found, 440 can be eliminated. leaving option a) 430 as answer. Not the right approach of solving though.

---

I have done it in 420. Donot know where is it incorrect.

s-a-c-e-s-c-d-t-b-a-d-f-t-f-e-d-e-s.

Even in this paper I had shown two incomplete questions to the examiner in exam hall and both are given marks to all I think

---

The path should start from t and end at s, which is exactly what is missing.

---

@srestha You missed the edge bd

Answer 1

The way to approach this question is to know that proof of "Euler Circuit" problem. Know the proof to get the idea why the following that I am writing, makes sense.
Here we have 4 vertices of odd degree, so, Euler circuit doesn't exist But if you still want to go from S to S by visiting every edge at least once and with minimum cost (i.e. visiting every edge at least once and as minimum repetition as possible) then for every odd degree vertex you have to re-visit one edge incident on that vertex. So, to get minimum cost,
For S, you can revisit(i.e. visit two times ) s-a (cost 10)
For t, f, you can revisit(i.e. visit two times ) t-f (cost 20)
For b, you can revisit(i.e. visit two times ) b-a (cost 20)

So, 380 + 20 + 20 + 10 = 430

Comments

@Deepak Poonia
I have come up with a walk from s to s, with lowest weight 430.
https://gateoverflow.in/?qa=blob&qa_blobid=12050191596893264254

---

@sadhak_25, that's correct. Exactly same point I have written in the above answer. The edges you have visited twice, are the same edges I mentioned in the answer above. 

---

Yes, my intention was to show an actual walk based on your solution.