1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.
  2. Hi Guest, welcome to the TES Community!

    Connect with like-minded education professionals and have your say on the issues that matter to you.

    Don't forget to look at the how to guide.

    Dismiss Notice

Chinese Postman problem

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

  1. briceanus

    briceanus New 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
    Thanks in advance
  2. fieldextension

    fieldextension New commenter

    Can you provide a link to the paper or else a scanned version of the question?
  3. 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

  4. briceanus

    briceanus New commenter

    Does this work? My first attempt at pasting a picture.
  5. 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
  6. briceanus

    briceanus New commenter

  7. fieldextension

    fieldextension New 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. briceanus

    briceanus New commenter

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

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

Share This Page