Graph Colouring (or something similar

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
taby
Posts: 154
Joined: Thu Nov 01, 2007 8:39 pm UTC
Location: Canada

Graph Colouring (or something similar

Postby taby » Tue Dec 01, 2009 6:46 pm UTC

I am wondering about solutions to the graph colouring problem. I have looked around for quite a while and it seems that a brute-force type approach is required.

The problem I have at hand is like this:
A network has n nodes. Each node is connected to the other (n - 1) nodes. Assign integer numbers to all of the nodes and all of the connections in the network, so that each node and its (n - 1) connections do not possess duplicate numbers. Of course, this must be done using at most n numbers for the entire network, which seems to be where the problem stops being trivial and starts becoming a juggling act of sorts. As far as I can tell, this is pretty much the same as the total coloring problem for an n vertex graph where all vertices are of degree (n - 1).

Do you know if there is a non-brute force solution to this type of problem?

This is not for work or school. It actually has to do with my flower bed next spring. :)

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Graph Colouring (or something similar

Postby jaap » Tue Dec 01, 2009 7:08 pm UTC

For odd n there is an easy to construct solution.
Spoiler:
Draw the graph as a regular n-gon with all its diagonals. Give the n nodes the labels 1 to n in any order.
The edges of the graph come in n sets of (n-1)/2 parallel edges. Give all parallel edges in a set the same label, namely the label of the one node that none of the edges in the set connects to.
Example n=7:
graphcoloured.gif
graphcoloured.gif (5.91 KiB) Viewed 1294 times

I hope that was clear.

I'll see if I can find a way to do even numbers later.
For even numbers a similar construction works too:
Spoiler:
Draw the graph as a regular n-gon with all its diagonals.
Give all parallel edges of the graph the same label, and if there are any nodes left over that are not at the ends of those edges then give them the same label too. Do this with all n sets of parallel edges, giving each set a different label.

For even n, this construction uses only n/2 different labels on the nodes, each used twice. For odd n the nodes all have different labels.



[edited to add picture]
Last edited by jaap on Tue Dec 01, 2009 8:07 pm UTC, edited 2 times in total.

User avatar
MartianInvader
Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Graph Colouring (or something similar

Postby MartianInvader » Tue Dec 01, 2009 7:19 pm UTC

Most graph coloring problems involve coloring just the vertices, and the edges indicate when two vertices can't have the same color. You might want to re-cast your problem in that framework by changing all of your "nodes" and "connections" into vertices, and then having exacting two edges coming out of each "connection" vertex: one going to each "node" vertex in that connection.

The graph you'd get out of this has n disjoint copies of the complete graph on n vertices, and each of these subgraphs is connected to each of the others by exactly one edge. So you kind of have a "complete graph on n complete graphs on n vertices" thing going on.

Let's see... If there's any justice in the world, you can do this symmetrically so that each "node" vertex gets a different color. So what you need is a way to assign to each "edge", a value based on the values of its nodes so that all the edges coming out of each node have different colors.

If we let S be the set {1,...,n}, this means you want a symmetric function f from S x S to S, such that:
[math]f(a,a) = a.
f(a,b) \neq a if b \neq a.
f(a,b) \neq f(a,c) for c \neq b.[/math]
This guarantees your edges are different from the nodes they touch, and that edges coming from the same node are different colors.

Hm... there's gotta be a simple way to do this, but I'm not seeing it right now. I'll think about it a little more.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: Graph Colouring (or something similar

Postby greengiant » Tue Dec 01, 2009 7:48 pm UTC

Having quickly drawn out the n=4 version, I'm pretty sure there's no way to do this so that each node gets a different number. I think it should be doable in general though.

How about this? Given the complete graph on n nodes, it's simple enough to find an edge colouring using n colours. Once the edges are coloured in, just go round the nodes and give them each whatever colour hasn't been used in the adjacent n-1 edges. Done, no adjacent edges have the same colour and no node has the colour of an edge touching it.

Edit: Thinking about it, I'm not sure how simple it is to edge colour a complete graph with n colours. But it is certainly doable by Vizing's Theorem

User avatar
taby
Posts: 154
Joined: Thu Nov 01, 2007 8:39 pm UTC
Location: Canada

Re: Graph Colouring (or something similar

Postby taby » Tue Dec 01, 2009 11:41 pm UTC

Thanks for the help!

OK, so after reading these replies (all AWESOME), and a little sleep, I think I got it figured out a little...

I got this function:
[math]f(i, j) = \left\{
\begin{array}{l l}
j - (n - i + 1) & \text{if $j > n - i + 1$,}\\
j + i - 1 & \text{if $j \leq n - i + 1$.}\\
\end{array} \right.[/math]

This gives these (ridiculously silly looking) matrices for [imath]n = 5[/imath] and [imath]n = 4[/imath]:
[math]\textbf{M}(5) = \left[ {\begin{array}{c|c|c|c|c}
\bf{1} & 2 & 3 & 4 & 5\\
2 & \bf{3} & 4 & 5 & 1\\
3 & 4 & \bf{5} & 1 & 2\\
4 & 5 & 1 & \bf{2} & 3\\
5 & 1 & 2 & 3 & \bf{4}\\
\end{array} } \right] ,[/math]
[math]\textbf{M}(4) = \left[ {\begin{array}{c|c|c|c}
\bf{1} & 2 & 3 & 4\\
2 & \bf{3} & 4 & 1\\
3 & 4 & \bf{1} & 2\\
4 & 1 & 2 & \bf{3}\\
\end{array} } \right].[/math]
I take [imath]\textbf{M}_{ii}[/imath] to be the colour of the nodes (the non-diagonal entries produce a symmetric matrix, and represent the connections), and so in the case of an even number of nodes I'll have to go in and manually spruce up the last half of the diagonal in some way. This is not perfect, but it's better than nothing -- thank you guys, this totally helped me out of my rut!!

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Graph Colouring (or something similar

Postby Nitrodon » Wed Dec 02, 2009 12:55 am UTC

If n is even, then each color is shared by an even number of nodes. In particular, you can't make all nodes the same color. This can be shown by noticing that the number of nodes with an incident edge of that color is also even.

However, for even n, it's possible to make all nodes the same color. I'm not sure how the aesthetics of that would work out, but I thought I'd mention it anyway.

EDIT: I'm not sure what I was thinking when I said that was possible for all n.
Last edited by Nitrodon on Wed Dec 02, 2009 3:19 am UTC, edited 1 time in total.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Graph Colouring (or something similar

Postby Tirian » Wed Dec 02, 2009 3:09 am UTC

Jaap's picture for odd n is correct, and for even n, you can just plop a vertex in the middle of the diagram and for each color attach an edge of that color joining the center vertex to the one that is not represented by that edge color. So the subgraph of each color's edges in that particular graphical representation would be a bunch of parallel edges and then one perpendicular edge radiating from the center.

For even n, it's closely related to the problem of finding a round-robin tournament between 2n players that can be accomplished in (2n-1) rounds. (In graph theoretical terms, that is saying that [imath]K_2n[/imath] is 1-factorable.) It should be simple enough to find charts of that online.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Graph Colouring (or something similar

Postby jaap » Wed Dec 02, 2009 6:16 am UTC

Tirian wrote:Jaap's picture for odd n is correct, and for even n, you can just plop a vertex in the middle of the diagram and for each color attach an edge of that color joining the center vertex to the one that is not represented by that edge color. So the subgraph of each color's edges in that particular graphical representation would be a bunch of parallel edges and then one perpendicular edge radiating from the center.


That does not quite work - you have added edges of the same colour as the nodes you are connecting them to. However, you have a graph now where every node has n edges that use n different colours. To fix it to satisfy the requirements, you then have to colour all the nodes with the (n+1)th colour.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Graph Colouring (or something similar

Postby Tirian » Wed Dec 02, 2009 2:42 pm UTC

Oh, I misunderstood. I couldn't figure why you were coloring the vertices too.

Right, then what you do is take Jaap's solution for odd n, plop down a center vertex, and then join that to every other vertex and color that new edge the color that was previously used for that vertex, and then color all of the vertices a new color. And there's no way to do better than that, because each vertex is incident upon as many colored elements as there are colors as it stands.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests