| Author |
Message
|
| MagiMaster |
 Posted: Wed Apr 16, 2008 12:58 am Post subject: Graph coloring algorithm |
 |
|
Forum Junior
Joined: 16 Jul 2006
Posts: 247
|
I know that I haven't solved the Graph Coloring problem with this, but since I mentioned it in another thread, I thought I'd post it and see if anyone else can see a simple graph it won't work on.
Steps:
1. Write out every node in the graph, sorted by degree (highest first).
2. Circle the first node in the list.
3. Cross out every node adjacent to the circled node.
4. Repeat 2 and 3 until all nodes are circled or crossed out. All circled nodes get the same color.
5. Repeat steps 1-4 on the crossed out nodes to get the next color.
I don't remember any more, but there might have been another step in there (between 3 and 4) sorting the remaining nodes by degree amongst themselves.
Anyway, this always produces a valid coloring, but it shouldn't be able to produce the best answer. |
|
| Back to top |
|
 |
| serpicojr |
| Posted: Wed Apr 16, 2008 9:07 am Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| Try running this algorithm on a complete graph. |
|
| Back to top |
|
|
| MagiMaster |
| Posted: Wed Apr 16, 2008 9:36 am Post subject: |
|
|
Forum Junior
Joined: 16 Jul 2006
Posts: 247
|
| Step 3 will cross out every node (except the circled one) which then move on to become other colors, so, at each level, only one node is assigned a color. It works on complete graphs at least. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Wed Apr 16, 2008 9:55 am Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| Oh, yeah, it works on complete graphs. It works on any graph--you already knew this. You were wondering whether it always produced the best solution. So how many colors does it use to color the complete graph? |
|
| Back to top |
|
|
| MagiMaster |
| Posted: Wed Apr 16, 2008 10:18 am Post subject: |
|
|
Forum Junior
Joined: 16 Jul 2006
Posts: 247
|
| It'll use n colors. Plus, I can't imagine how to color a complete graph otherwise. It seems like, for graph theory at least, the border cases (complete, empty, disjoint) are the easiest. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Wed Apr 16, 2008 4:34 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| Exactly, this uses the worst possible number of colors. But it always works! |
|
| Back to top |
|
|
| MagiMaster |
| Posted: Thu Apr 17, 2008 11:22 am Post subject: |
|
|
Forum Junior
Joined: 16 Jul 2006
Posts: 247
|
For now, I'm trying to find an example of something it doesn't work (perfectly) on though. It seems to give the right answer on most small graphs I've tried.
Does anyone know of any way to prove that this algorithm couldn't always find the best answer, no matter how things were sorted in step 1 (assuming they were still sorted consistently)? |
|
| Back to top |
|
|
| serpicojr |
| Posted: Thu Apr 17, 2008 2:42 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
Oh, right, I failed to note that the complete graph clearly can't be colored by less than n colors.
Um... yeah, I don't know how to show what you're asking, although I agree that your algorithm shouldn't always give the best answer. |
|
| Back to top |
|
|
|
|
