The graph theory thread

[GeekDog]

OK, following the discussion earlier I'm going to try and explain a little about graph theory, which I've been studying at college lately. It's pretty relevant to a lot of areas of computing as it is closely related to network theory, and it also forms a large part of the work I'm doing for my PhD. Best of all, the basic ideas behind it are very simple, so it's something everyone can understand...


So, what is a graph?

It is an abstract theoretical structure, which can be defined very simply by taking a set of points (called <i><b>nodes</b></i> or <i><b>vertices</b></i>). You can then join together some of the nodes with lines, which are called <i><b>edges</i></b>. This is a graph. Strictly speaking, no node should be connected to itself, and no two nodes should have more than one edge going between them.

You can draw a graph, and this is how I got onto the subject in the first place on this site: there are infinitely many ways of drawing the same graph, because the abstract idea of a graph tells you nothing about what goes where, merely which nodes are connected (and of course how many nodes there are). This can make it a little difficult to judge what the neatest way of drawing a graph might be, for instance drawing it so that none of the edges cross each other.


A few basic types of graph:

An empty graph En (n should be a subscript but I have no idea how to do such things!): this is just a set of n nodes, without any edges at all

A complete graph Kn: a graph with n nodes where every node is connected to every other node. The graph K5 (and greater) is non-planar; i.e. it cannot be drawn on a flat piece of paper without some edges crossing.

A complete bipartite graph Kn,m: a graph with nodes in two groups - one group of n nodes, and another group of m nodes. The nodes <i>within</i> a group are <b>not</b> connected to each other, but they <i>are</i> connected to all the nodes in the other group.

Question: What's the smallest complete bipartite graph that is non-planar?


You can make things more complicated, by making edges one-way (a directed graph or digraph) or by adding numbers to edges (a network). You can also allow edges to connect more than one node (a hypergraph).


This is only a very brief overview, depending on what people make of this we can always put up more info and discuss further. Thought it might be of some interest as there was some confusion about what a theoretical graph was (as opposed to the graphs you draw at school or in science, usually with an x and y axis, which aren't quite the same thing...). As i said at the beginning, it's also quite a straightforward area to get into, quite useful for computing, but doesn't seem to get taught to many people (the course i'm doing is a 3rd year undergrad maths course!). I'm sure a great lot of people have used some graph/network algorithms without knowing that's what they were (e.g. (minimum) spanning tree, shortest path through a network, travelling salesman problem).


One final question for you (which is pretty difficult to figure out, and even harder to prove - it's way beyond me to prove it!): what's the smallest number of colours you need, if you have a planar graph and want to colour every node so that no node has the same colour as any of its neighbours?

[leas5040]

4.

And now a difficult question for you: what is the answer if instead of planar graphs we consider graphs that can be embedded in a torus?

Any explanation as to why it is 4?

[Alvaro]

Sorry I accidentally deleted my post.

You can easily convince yourself that at least 4 colors are needed (try to color K4). The fact that 4 is enough is known as the Four-Color Theorem. The more general theorem for graphs in any surface is called Heawood Conjecture. For the torus, for example, the answer is 7.

[Bugdude]

I'm starting to wish I had studied graphy theory when I was doing my CS degree—it was probably taught in one of those boring subjects that I'm now wishing I hadn't avoided.

[leas5040]

I'm starting to wish I had studied graphy theory when I was doing my CS degree—it was probably taught in one of those boring subjects that I'm now wishing I hadn't avoided.

Are you starting to encounter this stuff where you work, or just something that you wish to learn?

Edit: Thanks Alvaro.

[Bugdude]

I'm starting to wish I had studied graphy theory when I was doing my CS degree—it was probably taught in one of those boring subjects that I'm now wishing I hadn't avoided.

Are you starting to encounter this stuff where you work, or just something that you wish to learn?

It's interesting and I wished I'd learnt it.

[leas5040]

I'm starting to wish I had studied graphy theory when I was doing my CS degree—it was probably taught in one of those boring subjects that I'm now wishing I hadn't avoided.

Are you starting to encounter this stuff where you work, or just something that you wish to learn?

It's interesting and I wished I'd learnt it.

It's never too late to start, unless you are dead. In that case, yes, it is too late to start. Who knows, maybe you could start posting questions here!

[Bugdude]

Perhaps, but I don't have much spare time to learn things I like anymore.

[GeekDog]

There's always time to learn, just find an excuse to drag it into your work and learn it as you go along. That's how i learnt C++, managed to talk my way into a job programming for a research group and then had to learn very quickly when i realised i knew nothing about how to program

Besides, if you've got the time to answer so many of our newbie questions, why can't you spare a bit to ask some yourself, as leas5040 pointed out?


Alvaro, nice one on the colouring theorem, didn't know the result for the torus (although it did cross my mind the other day that there might be some interesting results with different topologies)..

[GeekDog]

This might be of some interest to you guys, it's an application of graph theory to a biological problem: p53 Network and Biological Hackers (pdf format)