Graph theory - John C. Kirk
Jul. 25th, 2006
01:42 pm - Graph theory
I've recently been going through my LJ archive and "tagging" my old posts, and that is now basically done. There are some cases where I've introduced a new tag after referring to the subject a few times, so the previous posts now have an incomplete set of tags, but this is good enough for now, and should make it easier to find old posts.
Actually, I've found it vaguely interesting to read through the archive, particularly with the benefit of hindsight, where I know which plans worked out well and which ones didn't. That does confirm my general philosophy that I'm primarily writing for myself, rather than an audience, so it doesn't bother me if nobody comments on my posts.
That said, there are a couple of particular posts which I think are worth resurrecting, based on my MSc. Firstly, the challenge of the stapler - people who've started reading my LJ recently may not have seen it, and I like to think it's quite a funny story. Secondly, my algorithmic graph theory exam - now that I've sorted out a sensible way of including images in my posts I think I can do a "remastered" version of that post to explain the puzzle more clearly. You don't need any particular Maths/CompSci background to understand it, although that might give you a better sense of the context involved. (If you're interested in solving the puzzle, you might want to scroll down slowly so that you don't see the solution pictures before you've made your own attempt.)
The idea here is that we're dealing with graphs, i.e. a set of vertices (nodes) that are connected together with edges (lines). Although people use the word "graph" to refer to things like "bar graphs", they should really be called "bar charts" - a graph is a more general version of a tree diagram (i.e. all trees are graphs, but not all graphs are trees). A general rule for graphs is that you can't have two edges connecting the same pair of vertices unless they're pointing in different directions; this puzzle uses undirected graphs, so there can only be one edge between any two vertices. In this specific context you also can't have an edge connecting a vertex to itself, although that is sometimes allowable.
If you think about a map of London Underground, where you have one circle for each station and then lines joining them together, that's the basic idea. So, suppose that you have 4 vertices, each of which is connected to 3 edges - this means that every vertex will be connected to every other vertex. You could then draw that graph like this:
More specifically, we're dealing with planar graphs. That means that you can't have edges overlapping each other. So, we can redraw the previous graph like this:
This is perfectly valid, but it's a bit more elegant to rearrange the vertices/edges a bit, so that it looks like this:
In the exam question, this was described as T3, i.e. the graph of 4 vertices where each one has degree 3. ("Degree" is the number of edges coming out of each vertex.) Kn seems to be a fairly standard notation for "complete" graphs, e.g. K5 is a graph with 5 vertices which are all connected to each other. However, I haven't encountered the Tn notation anywhere else, so it may just have been made up for the purposes of that question.
The actual question involved drawing three graphs: T3 (as above), T4 (6 vertices of degree 4), and T5 (12 vertices of degree 5). This is related to Euler's formula, which tells you how many faces you will have (a "face" being like the face of a die, i.e. an area enclosed by edges), but you don't need to worry about the details of that to solve the puzzle.
So, next up is T4. My first attempt came out like this:
and then I was able to straighten out the edges to produce this:
The place where I got stuck in the exam was T5 - I spent a while doodling with various pictures, but couldn't get one to work, and eventually I ran out of time. However, it nagged at my brain afterwards, so I kept poking at it, and figured out the solution a few days later. Hint: It is significant that T3 and T4 both have triangular faces in their neat versions, i.e. T5 does too. Similarly, the neat versions of T3 and T4 could be treated as 3D objects rather than 2D graphs. Anyway, I'll post the answer later, once I've either dug it out from my old notes or re-solved it. In the meantime, feel free to attempt it yourselves...
I think this is an interesting type of exam question. It's not covered in the textbook, or in any of my notes from lectures, and I haven't been able to find any explicit solutions on the web. So, that meant that we had to figure it out for ourselves in the exam, i.e. by thinking rather than just regurgitating information, while under certain time pressure. On the other hand, since it was considered feasible for us to figure out in a fairly short space of time, that meant that it couldn't be an insanely difficult question, and arguably it's better to reward people for understanding the subject rather than just being able to recite facts from a book, as well as not penalising people for having a brief "brain fart" and forgetting one formula. It also has the advantage that you know if you've got it right, because all you have to do is count the edges at each vertex. Bottom line, I'd say that this type of question is nice if you're good at the subject, which I am (or was), so I'm happy with it.
(Incidentally, my estimated result for that exam was a bit optimistic, as seen here.)
Edit: the solution to T5 is now in the comments.