Chinese Postman problem

Discussion in 'Mathematics' started by briceanus, Feb 18, 2012.

1. briceanusNew commenter

I'm teaching myself D1 to support a couple of students doing the same this year. All OK except for one question on AQA D1 Jan11 paper. Q5.
After working out an optimal route, the question asks for the number of times vertex F is visited during the optimal route. Vertex F has 4 edges joining it and it is 'in the middle' of the network.
For similar questions, I've simply thought 1 in 1 out for each visit, hence 2 visits altogether.
The mark scheme simply says '3'. For 1 mark, why is this so obvious. Would I be expected to work out an optimal route (8 vertices) for 1 mark ?
Then the next question asks for the number of times vertex H is visited, again for 1 mark. H also has 4 edges (1 of which was added to stop it being 'odd'.)
The answer to this is given as 2 (as I would have thought anyway). H is on the 'outside' of the network.
Am I missing something REALLY obvious
Bric

2. fieldextensionNew commenter

Can you provide a link to the paper or else a scanned version of the question?

3. lizziec

Did you get the answer to the shortest chinese postman route correct?...
I haven't worked through the whole question, but it looks as if the "doubled edges" to cope with the odd nodes would need to go via F to get the shortest length (90 + 15 is less than 120 from H to E... en route to B, another odd node), which would give you the extra visit...
I hope this helps
Liz

4. briceanusNew commenter

Does this work? My first attempt at pasting a picture.

5. lizziec

I found it here! http://www.aqa.org.uk/qualifications/a-level/maths/mathematics/mathematics-key-materials
then click on past papers and select Jan 11, D1

No !!!

7. fieldextensionNew commenter

Liz is correct. The markscheme confirms this. Focus on where the figure of 210 came from in part (b) of the question. (90+210)

8. briceanusNew commenter

Of course, thankyou. That's a bit sneaky for 1 mark though.
Bric

Otherwise I assume it is always 1 in 1 out for non-starting vertices.