OCR (non mei) D1 Wednesday 15th June 2016

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 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)

Not really feeling confident for D1, could somebody briefly run through graph theory basics please? I feel least confident in this.

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?

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

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.

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

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

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 :'

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?

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

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*

Does anyone have access to the 2015 paper?

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?