?

Log in

No account? Create an account

Graph theory - John C. Kirk

Jul. 25th, 2006

01:42 pm - Graph theory

Previous Entry Share Next Entry

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:

Graph with overlapping edges

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:

T3 (messy)

This is perfectly valid, but it's a bit more elegant to rearrange the vertices/edges a bit, so that it looks like this:

T3 (neat)

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:

T4 (messy)

and then I was able to straighten out the edges to produce this:

T4 (neat)

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.

Comments:

[User Picture]
From:pozorvlak
Date:July 25th, 2006 05:47 pm (UTC)
(Link)
I got it by random poking (drew first vertex, fanned out, always leaving myself some space) on the second go, but it felt like the answer should have been obvious for some larger reason. I'd wondered about the numbers 5 and 12, but hadn't made the connection with Euler's formula. Gah! It's the dual graph of the regular dodecahedron, which you can project onto a plane using stereoscopic projection from the sphere.

Stapler story: this is why you should always carry a penknife :-) Incidentally, if you're still wondering whether to buy one, I can make the "how many blades" question easy: you want an Explorer Swiss Army Knife. Best blade combination at a sensible size in their range. Try the linked site, or eBay usually have them. Or Scout Shops, which often give student discounts. Or if you're feeling a bit richer, the Leatherman Juice XE6 looks very nice... eBay could be cheaper, but they don't turn up all that often IIRC. The problem with most Persons of Leather is that the blades lock, so it's actually illegal to carry them around without good reason. Lovely workmanship, though.
(Reply) (Thread)
[User Picture]
From:pozorvlak
Date:July 25th, 2006 05:56 pm (UTC)
(Link)
Incidentally, I used the wire-stripper on my Swiss Army Knife for the first time the other day. It's surprisingly effective...
(Reply) (Parent) (Thread)
[User Picture]
From:johnckirk
Date:July 25th, 2006 06:35 pm (UTC)
(Link)
It's the dual graph of the regular dodecahedron, which you can project onto a plane using stereoscopic projection from the sphere.

Yup, that sounds about right :) At the bottom of this page, it says "On the sphere, 4 vertices implies an average degree 3 (tetrahedron), 6 implies 4 (octahedron), 12 implies 5 (icosahedron)". I can certainly recognise the neat diagram that I drew for T3 as a tetrahedron, and it seems reasonable that my diagram for T4 is an octahedron (assuming a bottom face in 3D), although I'm not familiar enough with that shape to recognise it, and it didn't match any of the diagrams here. As for the icosahedron, I don't even recognise that word, although "dodecahedron" sounds familiar (in the context of pentagons/hexagons). We covered stereoscopic projection in the lecture course, although it does seem to hinge on choosing the right point on the sphere to project from.

As for the penknife, I do now have a small one (courtesy of princesslen) with one blade - I'm not sure what happened to my old Swiss Army Knife, unless it's still buried in one of the boxes I haven't unpacked yet (ahem). That did have a locking blade, and I used to use it on almost a daily basis when I was at school, e.g. for slicing through the tubes on the big cardboard boxes full of milk that go into fridges. Following on from susannahf's list of "strange requests on first aid duties", someone did ask me for tweezers the other day, which we don't have in our standard first aid kit (hygiene reasons?); I had a pair in the end of the pen-knife, although I never found a use for the toothpick on the other side, and it does seem a bit gross to reuse something like that. Anyway, I'm ok for now, but I will probably go for a more deluxe version in due course...
(Reply) (Parent) (Thread)
[User Picture]
From:pozorvlak
Date:July 25th, 2006 06:45 pm (UTC)
(Link)
Ah, of course, it is an icosahedron. An icosahedron is a polyhedron with 20 faces, all of which are triangles. It's dual to the dodecahedron, in the sense that if you put a vertex in the middle of every face of a dodecahedron and an edge crossing every edge of the dodecahedron, you get an icosahedron (and vice-versa). Similarly, the cube and the octahedron are dual to each other. The tetrahedron is self-dual. As for the octahedron: take the four vertices in the middle, and arrange them in a square. Now put the other two on top and underneath, to form a pair of pyramids joined at the base.
(Reply) (Parent) (Thread)
[User Picture]
From:johnckirk
Date:July 25th, 2006 10:32 pm (UTC)
(Link)
Ok, that makes sense. For the octahedron, my messy T4 diagram does sort of look like two pyramids end-to-end if you ignore the curve at the top, then do the "magic eye" thing and imagine which vertices are sticking forwards/backwards.

For the T5, I found this page quite handy - the planar image isn't much good (far too many vertices), but I've been able to draw a messy picture that resembles the 3D image on the right hand side:
Messy T5

I assume that it's possible to straighten out all the curves, so I'll try that next.
(Reply) (Parent) (Thread)
[User Picture]
From:johnckirk
Date:July 25th, 2006 10:55 pm (UTC)
(Link)
Ah yes, and here we go:
T5 (neat)

I'm not quite sure about that block in the middle - there's probably a neater way of drawing that. Still, I've got rid of the curves, so that's good enough for now.

I do wonder whether I lost a few marks in the exam, if my diagrams had curves rather than straight edges - I certainly remember a lot of scribbled out messes all over my paper!
(Reply) (Parent) (Thread)
[User Picture]
From:pozorvlak
Date:July 26th, 2006 12:03 pm (UTC)
(Link)
I do wonder whether I lost a few marks in the exam, if my diagrams had curves rather than straight edges

I doubt it. Part of the point of graph theory is that the shapes of the edges doesn't really matter :-)

Incidentally, this discussion of regular polyhedra suggests that the fact that the faces are triangular in your examples isn't all that important: for instance, try drawing a planar graph with eight vertices of degree three, or a planar graph with twenty vertices of degree three...
(Reply) (Parent) (Thread)
[User Picture]
From:johnckirk
Date:July 26th, 2006 12:31 pm (UTC)
(Link)
Regarding the triangular aspect, that was something I found when I was digging through my old emails. Basically, I emailed the PhD student who helped out with our lecture course after the exam to say "Now that it won't affect my result, can you tell me the answer to T5 for my own curiosity?" His reply was:

T3 and T4 - notice anything in common between them ? Let me tell you
that all the faces are triangular, i.e. they are both triangulations. So now you know that you are looking for a triangulation with 12 vertices, the rest should follow :)


My first attempt at a graph with 8 vertices of degree 3 involved two pentagons stuck together on their "bottom" sides, although that also involves one edge overlapping two others, so it's not planar. So far I've been doodling the images on paper, then using MS Paint to create the images that I've uploaded here - it occurs to me that there's probably scope for a little drag-and-drop application to help people play with this stuff.
(Reply) (Parent) (Thread)
[User Picture]
From:susannahf
Date:July 26th, 2006 11:13 am (UTC)
(Link)
There's nothing wrong with having tweezers in a first aid kit so long as you have something to sterilise them with, and you don't go digging around for stuff (that tends to cause more harm than good).

In OUFAU, we only have them in our "orange boxes", which live in static first aid rooms, where you are more likely to have sufficient light. I recently used one to successfully remove a long shard of glass from a foot, which was very satisfying, particularly for the patient who didn't have to go to A&E.
(Reply) (Parent) (Thread)