The D1 exam is but a week off, friends, and hopefully you've been practising all the algorithms and stuff. There is one aspect that I'm having trouble with, so I thought I'd try and right up a little revision sheet for us all, unless you're reading this in the future, in which case I have undoubtedly become a shining blogging god, and thanks to my own last post no one ever took a Decision Maths exam again, instead opting for nicer, more productive modules like Mechanics, or Further Maths. Indeed, anyone taking a D𝒙 exam is actually brought into a psychologist's lab to help further understand why someone would subject themselves to such a thing. Good luck, strange person I just made up. May you find peace in your future.
Anyway, the thing I want to work on right now is definitions. I haven't had to properly equate lists of uncommon words and phrases with arbitrarily specific meanings since learning all the Italian for Music Theory, so I'm not looking forward to it. Best get it done though. I'll try to keep things minimal, and only go into the particularly arcane ones. You should be able to remember something like "A subgraph is part of a graph" yourself. For the more tricky ones I'll try to single out the words to remember that might help jog your memory.
Path - A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
Ok, you see what I mean? It's not enough to just say that it's a bunch of connected vertices. You have to be ultra specific, to the point of obfuscation. I'm pretty sure Decision is Mathematicians' way of trolling Biology and Law students.
Keywords: finite sequence, no more than once
Walk - a path where you are permitted to return to vertices more than once.
So, a path can only visit each point once, whereas if you are walking along said path, you can go wherever the devil you like.
Keywords: more than once
Cycle - A closed path
a path where you could conceivably go around in a circle if you followed it. These are the things you want to avoid in them there Prim and Kruskal problems.
Spanning tree - A subgraph of graph G containing all the vertices of graph G and is a tree.
Define tree with tree. Stay classy Decision Maths.
Keywords: subgraph, tree
Isomorphic Graph - Shows the same information but differently.
If you're coming at this from a more scientific background you should recognise the prefix iso, meaning "equal". Isotope is a variant on an element that occupies the same τόπος (tópos, “place”) on the periodic table. Isomer is something that has the same molecular formula, but a different structure (μέρος (meros, “part”))1 .
Keywords: Iso-same, morphic-shape
Complete graph - a graph in which every vertex is directly connected by an edge to each of the other vertices.
Everything is connected to everything, lines are everywhere.
Keywords: Every vertex, connected
Bipartite graph - consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
Pretty simple one, it's just describing the set up of your average bipartite problem.
Alternating path - starts at an unmatched node on one side of a bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternatively 'not in' and 'in' the initial matching.
This is another one of those definitions that really takes the piss. It basically means that an alternating path is a path that alternates, specifically between the two sets of nodes. It is what you end up with after applying the maximum matching algorithm.
It is probably best split into it's two parts. Try to associate everything in red with "path" and everything in blue with "alternating". The second one should be easier as "alternatively" is right in there already.
Keywords: Starts unmatched, finishes unmatched, initial matching
Matching - The one-to-one pairing of some or all of the elements of on set, X, with elements of a second set, Y.
The main thing I can recommend for this one is DO NOT FORGET the "one-to-one" bit. That is worth , well, probably only a single mark, but any mark you can grab in this exam is a good one. It is simply not enough to just say that it's the pairing of the two sets.
Keywords: one-to-one pairing, some or all
Complete matching - This is the same as a compete graph but with matching replacing the word graph, and taking into account the two separate sets. It is possible that you cannot obtain a complete matching if some tosser in the question refuses to do some task or another. In this case you simply get as many pairs are you can and call the a maximal matching.
Valency - This is essentially the number of arcs that are connected, or "incident" to a particular vertex. This can be either odd or even, because, you know, integers work that way.
Eulerian - A graph has this property if all the valencies in it was even. If precisely 2 valencies are odd, and the others even then this is known as being semi-Eulerian
Traversable - A graph is traversable if it is possible to traverse every arc once without removing pen from paper. This fits with the Eulerian definition as is a graph is Eulerian, it is traversable. Indeed, if a graph is semi-Eulerian is it semi-traversable, with the start and end points being the two odd valencies.
Sink node - The last one.
Dummy activity - A virtual line with no time value, used to show that an activity depends on another before starting, if said activity has already been drawn leading to another node.
Early event time - The earliest time of arrival at the event allowing for the completion of all preceding activities. Calculated during the forward pass/scan.
Late event time - The latest time that the event can be left without extending the time needed for the project. Calculated during the backwards pass/scan.
Critical activity - If any increase in an activity's duration with cause an increase in the total duration of the project then it is a critical activity. The path leading from source node to sink node following these activities is the critical path.
And that, as they say, is that. I've left out linear programming as that is basically algebra, and we all know algebra terms. Inequalities and all that. I have on the other hand added a few potentially superfluous ones just for completions sake. I can't say I've heard much call for a definition of source/sink node.
Good luck, all.
1I could go on, and I really want to because etymologies are fascinating, but I kinda committed to this revision thing.
Read more
Anyway, the thing I want to work on right now is definitions. I haven't had to properly equate lists of uncommon words and phrases with arbitrarily specific meanings since learning all the Italian for Music Theory, so I'm not looking forward to it. Best get it done though. I'll try to keep things minimal, and only go into the particularly arcane ones. You should be able to remember something like "A subgraph is part of a graph" yourself. For the more tricky ones I'll try to single out the words to remember that might help jog your memory.
Graphs and Networks
Graphs understandably hold a whole bunch of the words you need to remember, taking up most of the course as they do.Path - A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
Ok, you see what I mean? It's not enough to just say that it's a bunch of connected vertices. You have to be ultra specific, to the point of obfuscation. I'm pretty sure Decision is Mathematicians' way of trolling Biology and Law students.
Keywords: finite sequence, no more than once
Walk - a path where you are permitted to return to vertices more than once.
So, a path can only visit each point once, whereas if you are walking along said path, you can go wherever the devil you like.
 |
| And with scenes like this, why not? |
Cycle - A closed path
a path where you could conceivably go around in a circle if you followed it. These are the things you want to avoid in them there Prim and Kruskal problems.
Spanning tree - A subgraph of graph G containing all the vertices of graph G and is a tree.
Define tree with tree. Stay classy Decision Maths.
Keywords: subgraph, tree
Isomorphic Graph - Shows the same information but differently.
If you're coming at this from a more scientific background you should recognise the prefix iso, meaning "equal". Isotope is a variant on an element that occupies the same τόπος (tópos, “place”) on the periodic table. Isomer is something that has the same molecular formula, but a different structure (μέρος (meros, “part”))1 .
Keywords: Iso-same, morphic-shape
Complete graph - a graph in which every vertex is directly connected by an edge to each of the other vertices.
Everything is connected to everything, lines are everywhere.
Keywords: Every vertex, connected
Bipartite graphs
This is a fairly important part, as almost every bipartite question I've done has asked for some definition or another. As such I've seperated it from the other graph definitions. |
| Not to be confused with... |
Bipartite graph - consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
Pretty simple one, it's just describing the set up of your average bipartite problem.
Alternating path - starts at an unmatched node on one side of a bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternatively 'not in' and 'in' the initial matching.
This is another one of those definitions that really takes the piss. It basically means that an alternating path is a path that alternates, specifically between the two sets of nodes. It is what you end up with after applying the maximum matching algorithm.
It is probably best split into it's two parts. Try to associate everything in red with "path" and everything in blue with "alternating". The second one should be easier as "alternatively" is right in there already.
Keywords: Starts unmatched, finishes unmatched, initial matching
Matching - The one-to-one pairing of some or all of the elements of on set, X, with elements of a second set, Y.
The main thing I can recommend for this one is DO NOT FORGET the "one-to-one" bit. That is worth , well, probably only a single mark, but any mark you can grab in this exam is a good one. It is simply not enough to just say that it's the pairing of the two sets.
Keywords: one-to-one pairing, some or all
Complete matching - This is the same as a compete graph but with matching replacing the word graph, and taking into account the two separate sets. It is possible that you cannot obtain a complete matching if some tosser in the question refuses to do some task or another. In this case you simply get as many pairs are you can and call the a maximal matching.
Route Inspection (aka Chinese postman problem)
I prefer to think of this as the envelope problem, because it reminds me of that puzzle we all did when younger of trying to draw an envelope without pen leaving paper or redrawing lines. It didn't take too long to work out that this was impossible without adding an extra line to make it look like an open envelope. If there is one thing I can say I enjoyed about D1 it's the joy of finally knowing why this was. Anyone, on to the definitions.Valency - This is essentially the number of arcs that are connected, or "incident" to a particular vertex. This can be either odd or even, because, you know, integers work that way.
Eulerian - A graph has this property if all the valencies in it was even. If precisely 2 valencies are odd, and the others even then this is known as being semi-Eulerian
 |
| Leonhard Euler. This guy has had an insane amount of stuff named after him |
Traversable - A graph is traversable if it is possible to traverse every arc once without removing pen from paper. This fits with the Eulerian definition as is a graph is Eulerian, it is traversable. Indeed, if a graph is semi-Eulerian is it semi-traversable, with the start and end points being the two odd valencies.
Critical path analysis
Source node - The first one.Sink node - The last one.
Dummy activity - A virtual line with no time value, used to show that an activity depends on another before starting, if said activity has already been drawn leading to another node.
Early event time - The earliest time of arrival at the event allowing for the completion of all preceding activities. Calculated during the forward pass/scan.
Late event time - The latest time that the event can be left without extending the time needed for the project. Calculated during the backwards pass/scan.
Critical activity - If any increase in an activity's duration with cause an increase in the total duration of the project then it is a critical activity. The path leading from source node to sink node following these activities is the critical path.
And that, as they say, is that. I've left out linear programming as that is basically algebra, and we all know algebra terms. Inequalities and all that. I have on the other hand added a few potentially superfluous ones just for completions sake. I can't say I've heard much call for a definition of source/sink node.
Good luck, all.
1I could go on, and I really want to because etymologies are fascinating, but I kinda committed to this revision thing.
Posts
