You are Here: Home >< Maths

# OCR (non mei) D1 Wednesday 15th June 2016

Announcements Posted on
Would YOU be put off a uni with a high crime rate? First 50 to have their say get a £5 Amazon voucher! 27-10-2016
1. 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?
2. (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
3. (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)
4. (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
5. (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.
6. (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
cheers
7. (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
8. 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
9. (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*
10. (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 :')
11. (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
12. (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!

14. (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!

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?
15. (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
16. (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!
17. (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
18. (Original post by violavenisis)
Search maths dave on youtube he has a playlist which in the D1 2015 videos there;s a link to a paper
19. (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!

Same boat as you
20. 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?

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. Oops, you need to agree to our Ts&Cs to register

Updated: June 16, 2016
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

Poll
Useful resources