Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    3
    ReputationRep:
    Quick question - when finding the solution to the TSP, can nodes be visited twice?? I thought with the nearest neighbour method you weren't allowed to but on the spec it says "use short cuts when possible". Doesn't that imply visiting a node twice?
    Offline

    2
    ReputationRep:
    (Original post by Heisenberg___)
    Quick question - when finding the solution to the TSP, can nodes be visited twice?? I thought with the nearest neighbour method you weren't allowed to but on the spec it says "use short cuts when possible". Doesn't that imply visiting a node twice?
    In the actual algorithm no you can't, however i think afterwards they may ask you to improve on your algorithm in which you can revisit nodes twice as you are not using a formal algorithm
    Offline

    14
    ReputationRep:
    (Original post by SGHD26716)
    That paper was just disgusting.

    The D1 chief examiner is a joker. In D1 Jan 13, question 5 is a LP based in a bakery. The guy is called Roland Neede.

    (roll and kneed as you do to dough)
    Did you see the Dijkstra's question about a woman who liked to drive but avoid speed cameras - she was called Rhoda Raygh. (like road rage hahah)
    Offline

    10
    ReputationRep:
    (Original post by tobibo)
    Not really feeling confident for D1, could somebody briefly run through graph theory basics please? I feel least confident in this.
    Graphs are made up of vertices/nodes and arcs/edges.
    Or in other words vertices are dots that often represent places
    Arcs are lines linking them, that often represent things like roads between places.

    The amount of lines connecting to a node is its order. If a node has 3 lines connecting to it it has order 3, similarly if you are in the middle of a crossroad, there are 4 roads connecting so you could say it has order 4.

    Eulerian graphs are graphs that has an even order on every node, e.g the orders of the graph could be 2, 2, 2. Which would be a triangle. The most important thing about Eulerian graphs are that you can start at a node and end at the same node without repeating any arcs.

    Semi Eulerian graphs have exactly two odd nodes and the rest are even. The important thing about semi eulerian graphs are that you can start at one odd node and travel every arc once and end at the other odd node.

    Graphs with more than two odd nodes are not Eulerian or Semi Eulerian.

    A cycle or closed path is a route around a graph that brings you back to your starting point, e.g the graph must be Eulerian or you must make the graph eulerian.

    A tree or Minimum spanning tree is a graph that you can only get from one node to another via a certain path, for example a triangle with 3 nodes a b c isn't a spanning tree because you can get the start by going around. It's hard to explain without a graph.

    Imagine a running track, that is a cycle because you can get all of the way around without going back, a one way street could be seen as a minimum spanning tree because you cannot return to your starting point without going back on yourself. There is probably a better explanation than this somewhere.

    You have Kruskal and Prim's algorithms which helps you find a minimum spanning tree.

    Kruskal's algorithm
    1) Pick the arc of least weight
    2) Find the next smallest arc available
    - If it forms a cycle/closed path ignore it
    - if it doesn't form a cycle add it
    3) Repeat step 2 until all vertices are joined.

    Prim's
    1) Pick a vertex to start with preferably one connected to the smallest arc, unless you have been given one to start with.
    2) choose the arc of least weight that will connect to a vertex already in the tree, as long as it doesn't form a cycle.
    3) Repeat 2 until all vertices are connected.

    Dijkstras Algorithm is INCREDIBLY simple, if you don't understand it it can look quite scary, watch a few videos on youtube as it's hard to explain without an example.

    Route Inspection Problem
    You have to go along every arc and return at your starting point, remember what I said earlier about Eulerian graphs, you can only do route inspection if there are no odd nodes so sometimes if you have 2 odd nodes you will have to add a new arc between both making them both even nodes and therefore have a Eulerian graph.
    If you have 4 odd nodes you will have to look at the pairing of nodes e.g
    if you have 4 odd nodes A, B, C, D the arcs between them are thus
    AB = 5 CD = 6
    11 altogether
    AC = 6 BD = 8
    14 altogether
    AD = 10 BC = 5
    15 altogether

    11 is less than 14 and 15 so AB and CD is the shortest arcs to repeat, therefore making ABCD all even order but keeping the length of time of arcs as small as possible.

    Travelling Salesperson Problem
    Nearest Neighbour Algorithm (Upper Bound of TSP)
    Pick a vertex to start at, you'll often be given one to start at, pick the shortest arc connected to this, i.e 'nearest neighbour'. Pick the next nearest neighbour, i.e shortest arc as long as you haven't already visited it.
    Carry on and once all vertices have been visited return to start.

    Often a question will say "show that the Nearest Neighbour Algorithm fails started at A"
    If you start at A and the nearest neighbour is B, then the nearest is C, but say for example that C is only connected to A and B but you need to visit vertex D then the algorithm will fail because you cannot get to D without repeated other arcs.

    Lower Bound TSP
    The exam will tell you to delete a vertex, use Prims algorithm as discussed earlier to create a minimum spanning tree but ignoring the deleted vertex, after doing this add the two shortest arcs connecting to the deleted vertex and add them to the tree.

    Hope this helps
    Offline

    10
    ReputationRep:
    (Original post by Heisenberg___)
    Quick question - when finding the solution to the TSP, can nodes be visited twice?? I thought with the nearest neighbour method you weren't allowed to but on the spec it says "use short cuts when possible". Doesn't that imply visiting a node twice?
    I'm certain you aren't allowed to repeat nodes with the Nearest Neighbour however once you have visited all of the nodes and you are going back to the start you might be able to use a shortcut instead of going straight back to the start if there is a shortcut.

    I'm not 100% sure on the shortcut at the end but I know for sure you aren't allowed to use the same node twice before the end.
    Offline

    1
    ReputationRep:
    (Original post by JW22)
    Graphs are made up of vertices/nodes and arcs/edges.
    Or in other words vertices are dots that often represent places
    Arcs are lines linking them, that often represent things like roads between places.

    The amount of lines connecting to a node is its order. If a node has 3 lines connecting to it it has order 3, similarly if you are in the middle of a crossroad, there are 4 roads connecting so you could say it has order 4.

    Eulerian graphs are graphs that has an even order on every node, e.g the orders of the graph could be 2, 2, 2. Which would be a triangle. The most important thing about Eulerian graphs are that you can start at a node and end at the same node without repeating any arcs.

    Semi Eulerian graphs have exactly two odd nodes and the rest are even. The important thing about semi eulerian graphs are that you can start at one odd node and travel every arc once and end at the other odd node.

    Graphs with more than two odd nodes are not Eulerian or Semi Eulerian.

    A cycle or closed path is a route around a graph that brings you back to your starting point, e.g the graph must be Eulerian or you must make the graph eulerian.

    A tree or Minimum spanning tree is a graph that you can only get from one node to another via a certain path, for example a triangle with 3 nodes a b c isn't a spanning tree because you can get the start by going around. It's hard to explain without a graph.

    Imagine a running track, that is a cycle because you can get all of the way around without going back, a one way street could be seen as a minimum spanning tree because you cannot return to your starting point without going back on yourself. There is probably a better explanation than this somewhere.

    You have Kruskal and Prim's algorithms which helps you find a minimum spanning tree.

    Kruskal's algorithm
    1) Pick the arc of least weight
    2) Find the next smallest arc available
    - If it forms a cycle/closed path ignore it
    - if it doesn't form a cycle add it
    3) Repeat step 2 until all vertices are joined.

    Prim's
    1) Pick a vertex to start with preferably one connected to the smallest arc, unless you have been given one to start with.
    2) choose the arc of least weight that will connect to a vertex already in the tree, as long as it doesn't form a cycle.
    3) Repeat 2 until all vertices are connected.

    Dijkstras Algorithm is INCREDIBLY simple, if you don't understand it it can look quite scary, watch a few videos on youtube as it's hard to explain without an example.

    Route Inspection Problem
    You have to go along every arc and return at your starting point, remember what I said earlier about Eulerian graphs, you can only do route inspection if there are no odd nodes so sometimes if you have 2 odd nodes you will have to add a new arc between both making them both even nodes and therefore have a Eulerian graph.
    If you have 4 odd nodes you will have to look at the pairing of nodes e.g
    if you have 4 odd nodes A, B, C, D the arcs between them are thus
    AB = 5 CD = 6
    11 altogether
    AC = 6 BD = 8
    14 altogether
    AD = 10 BC = 5
    15 altogether

    11 is less than 14 and 15 so AB and CD is the shortest arcs to repeat, therefore making ABCD all even order but keeping the length of time of arcs as small as possible.

    Travelling Salesperson Problem
    Nearest Neighbour Algorithm (Upper Bound of TSP)
    Pick a vertex to start at, you'll often be given one to start at, pick the shortest arc connected to this, i.e 'nearest neighbour'. Pick the next nearest neighbour, i.e shortest arc as long as you haven't already visited it.
    Carry on and once all vertices have been visited return to start.

    Often a question will say "show that the Nearest Neighbour Algorithm fails started at A"
    If you start at A and the nearest neighbour is B, then the nearest is C, but say for example that C is only connected to A and B but you need to visit vertex D then the algorithm will fail because you cannot get to D without repeated other arcs.

    Lower Bound TSP
    The exam will tell you to delete a vertex, use Prims algorithm as discussed earlier to create a minimum spanning tree but ignoring the deleted vertex, after doing this add the two shortest arcs connecting to the deleted vertex and add them to the tree.

    Hope this helps
    wow this is helpful
    cheers
    Offline

    4
    ReputationRep:
    (Original post by Heisenberg___)
    Quick question - when finding the solution to the TSP, can nodes be visited twice?? I thought with the nearest neighbour method you weren't allowed to but on the spec it says "use short cuts when possible". Doesn't that imply visiting a node twice?
    That's where you change it after
    For example, you would compare the actual route (4 nodes at a time) with the route with the centre two nodes swapped around i.e comparing ABCD and ACBD to see which is quicker
    Offline

    10
    ReputationRep:
    Who still hasn't done all the past papers, I've only done like 3-4 but they all seem really similar. Worried about FP3 on Friday, still haven't learnt group theory.

    R.I.P me


    But then again..........I don't even need further maths
    Offline

    3
    ReputationRep:
    (Original post by JW22)
    I'm certain you aren't allowed to repeat nodes with the Nearest Neighbour however once you have visited all of the nodes and you are going back to the start you might be able to use a shortcut instead of going straight back to the start if there is a shortcut.

    I'm not 100% sure on the shortcut at the end but I know for sure you aren't allowed to use the same node twice before the end.
    Thank you!!

    (Original post by nutcase13)
    In the actual algorithm no you can't, however i think afterwards they may ask you to improve on your algorithm in which you can revisit nodes twice as you are not using a formal algorithm
    Amazing thanks

    (Original post by Gogregg)
    That's where you change it after
    For example, you would compare the actual route (4 nodes at a time) with the route with the centre two nodes swapped around i.e comparing ABCD and ACBD to see which is quicker
    But surely if A-C was shorter than A-B, the shorter one would've already been selected during Nearest Neighbour.

    screw this module, i need to ace c3 and 4 to get the a*
    Offline

    11
    ReputationRep:
    (Original post by Sonnyjimisgod)
    Who still hasn't done all the past papers, I've only done like 3-4 but they all seem really similar. Worried about FP3 on Friday, still haven't learnt group theory.

    R.I.P me


    But then again..........I don't even need further maths
    Go to physicsandmathstutor.com download all the FP3 groups question and just brute force your brain until you notice the patterns and how it all works, that's how I've done it :')
    Offline

    10
    ReputationRep:
    (Original post by rich1334)
    Go to physicsandmathstutor.com download all the FP3 groups question and just brute force your brain until you notice the patterns and how it all works, that's how I've done it :'
    Haha that's my plan, although I still don't fully understand the concepts. I am taking with FMSP (self-teach) and all the other topics (Diff. eqn., further complex, and even vectors) make sense, but group theory is so different I find it hard to comprehend with no teacher. I think that's what I'll end up doing though. The good ol' memorising mark scheme technique-proven failure lol

    Have you taken D2, I started learning the topics a week before the exam and was probably my best exam after FP1, that say's a lot about how the exams have gone so far
    Offline

    11
    ReputationRep:
    (Original post by Sonnyjimisgod)
    Haha that's my plan, although I still don't fully understand the concepts. I am taking with FMSP (self-teach) and all the other topics (Diff. eqn., further complex, and even vectors) make sense, but group theory is so different I find it hard to comprehend with no teacher. I think that's what I'll end up doing though. The good ol' memorising mark scheme technique-proven failure lol

    Have you taken D2, I started learning the topics a week before the exam and was probably my best exam after FP1, that say's a lot about how the exams have gone so far
    Yeah group theory is just weird and really doesn't have a place in A Level maths, it's totally unrelatable to anything!

    Are you doing the whole A2 FM in one year? That's brutal!

    This year I'm doing M2 (OCR consulted with Satan this year for that paper...), D1, C3, C4, FP2 and FP3. I need A*AA this year so 90 in C3 + C4 and 19 UMS in D1 so tomorrow isn't a big deal As long as I average 66 UMS in Further this year I should be safe for an A!

    What about you?
    Offline

    1
    ReputationRep:
    Does anyone have access to the 2015 paper?
    Offline

    10
    ReputationRep:
    (Original post by rich1334)
    Yeah group theory is just weird and really doesn't have a place in A Level maths, it's totally unrelatable to anything!

    Are you doing the whole A2 FM in one year? That's brutal!

    This year I'm doing M2 (OCR consulted with Satan this year for that paper...), D1, C3, C4, FP2 and FP3. I need A*AA this year so 90 in C3 + C4 and 19 UMS in D1 so tomorrow isn't a big deal As long as I average 66 UMS in Further this year I should be safe for an A!

    What about you?
    Damn son

    I don't need anything, on a gap year and already got unconditional offers so just thought I'd do this since it's related to my degree.

    Such a bad idea though, spent the first half of the year travelling, and now have two jobs and only do FM in the evenings if I've got time/not tired.

    Thought I could get an A*/A but now just hoping I get a B/C so it's not that embarrassing. So far take FP1, D2 and M2, and think I've got A's in them apart from the ridiculous M2 paper from hell!

    Where you off to uni?
    Offline

    11
    ReputationRep:
    (Original post by Sonnyjimisgod)
    Damn son

    I don't need anything, on a gap year and already got unconditional offers so just thought I'd do this since it's related to my degree.

    Such a bad idea though, spent the first half of the year travelling, and now have two jobs and only do FM in the evenings if I've got time/not tired.

    Thought I could get an A*/A but now just hoping I get a B/C so it's not that embarrassing. So far take FP1, D2 and M2, and think I've got A's in them apart from the ridiculous M2 paper from hell!

    Where you off to uni?
    Oh nice! Where have you travelled to?

    I'm hoping to do the same although not on such a grand scale, work at my job as a milkshake man through July and August, travel to Australia for the whole of September and step off the plane into Imperial if all goes to plan
    Offline

    10
    ReputationRep:
    (Original post by rich1334)
    Oh nice! Where have you travelled to?

    I'm hoping to do the same although not on such a grand scale, work at my job as a milkshake man through July and August, travel to Australia for the whole of September and step off the plane into Imperial if all goes to plan
    Sounds awesome!

    Went round east asia for a while, and then scandanavia. Couldn't afford flights to Australia but will definitely in the coming years.

    Wow imperial is sick!

    Good luck for all your exams!
    Offline

    1
    ReputationRep:
    (Original post by Heisenberg___)
    Thank you!!



    Amazing thanks



    But surely if A-C was shorter than A-B, the shorter one would've already been selected during Nearest Neighbour.

    screw this module, i need to ace c3 and 4 to get the a*
    bump
    Offline

    10
    ReputationRep:
    (Original post by violavenisis)
    Does anyone have access to the 2015 paper?
    Search maths dave on youtube he has a playlist which in the D1 2015 videos there;s a link to a paper
    Offline

    1
    ReputationRep:
    (Original post by rich1334)
    Yeah group theory is just weird and really doesn't have a place in A Level maths, it's totally unrelatable to anything!

    Are you doing the whole A2 FM in one year? That's brutal!

    This year I'm doing M2 (OCR consulted with Satan this year for that paper...), D1, C3, C4, FP2 and FP3. I need A*AA this year so 90 in C3 + C4 and 19 UMS in D1 so tomorrow isn't a big deal As long as I average 66 UMS in Further this year I should be safe for an A!

    What about you?
    Same boat as you
    Offline

    3
    ReputationRep:
    when you want to minimise a function instead of maximise, do you jnust multiply by -1?

    e.g. if you had C=3x+4y+2z, would it be C=-3x-4y-2z?
 
 
 
Poll
Do you agree with the PM's proposal to cut tuition fees for some courses?

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.