Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Colorful Algorithms: Solving Map-coloring and Related Problems : Page 2

It has been proven that you can always color a map with four colors in such as way that no two adjacent regions have the same color. Unfortunately doing so can be both difficult and time consuming—but it's not too hard to color a map with five colors.


advertisement
From Maps to Graphs
The five-coloring algorithm relies on two key observations. I'll describe the observations shortly but they are a bit easier to understand if you think in terms of graphs instead of maps. You can represent any map as a planar graph (a graph where the links do not cross each other). Convert the regions into nodes in the graph. Connect two nodes with links if the two corresponding regions are adjacent.

Figure 1 shows a map on the left and the corresponding graph on the right. Node A on the right has links to nodes B, C, D, and E because in the map on the left region A has neighbors B, C, D, and E.

 
Figure 1. Converting Maps to Graphs: You can convert any map into a planar graph.
In a graph, a node's degree is the number of links that it has In Figure 1, node D has degree six because it has six links (and the corresponding region D in the map has six neighbors). A node's neighbors are the nodes on the other ends of its links. In Figure 1, node D's neighbors are nodes A, C, E, G, H, and I.

Thinking in terms of a graph, the five-coloring problem is to color each node in the graph so that no neighboring nodes have the same color. Key Observations
The five-coloring algorithm uses two observations to convert a graph into a simpler graph that has the same color properties as the original. It then five-colors the simpler graph and uses the result to color the original more complicated graph. This will be easier to understand when you see an example.



The first observation is that you can easily assign a color to a node N that has degree less than five. If the node has fewer than five neighbors, those neighbors cannot use up all five of the available colors so at least one color remains for node N.

 
Figure 2. Simplifying Coloring: The figure illustrates Rule 1 for simplifying a graph and applying colors.
This leads to Rule 1 for simplifying the graph: For each node N with degree less than five, remove it from the graph, five-color the remaining graph, restore node N, and pick a color for it from the colors that are not used by its neighbors.

Figure 2 shows an example graphically. In the original graph on the left, node A has only two neighbors: B and C. Remove node A to get the second graph. Use your five colors to color the smaller graph (the third picture in Figure 2 where B and C are colored blue and yellow). Finally restore node A and give it a color that is not used by B or C (the last picture in Figure 2). For many graphs, Rule 1 suffices to produce a valid five-coloring. The logic translates to a programming loop: While the graph contains a node, find a node with degree less than five and remove it. Continue removing nodes until the graph is empty. Then start adding the nodes back into the graph in reverse order, assigning each node colors that are not used by its neighbors.

 
Figure 3. Too Many Neighbors: In some maps and graphs, every region or node has at least five neighbors, so Rule 1 won't work.
This method works as long you can always find a node with fewer than five neighbors. For example, you can five-color the graphs shown in Figure 1 and Figure 2 in this way. However, if every node has at least five neighbors, then Rule 1 doesn't work. Figure 3 shows a map and corresponding graph where every node has five neighbors. Because every node has degree five, you cannot use Rule 1 to simplify it.

To simplify this graph, you need to make a second more complicated observation. It can be shown (although not by me) that, if a graph contains no nodes with degree less than five, then you can find at least one node X with neighbors N1 and N2 where:

  • X has exactly five neighbors
  • N1 and N2 have at most seven neighbors
  • N1 and N2 are not neighbors of each other
 
Figure 4. Simplifying Graphs: The figure illustrates Rule 2 for simplifying a graph.
Now suppose we require that nodes N1 and N2 have the same color. Because they are not neighbors of each other, that is possible. Then because node X has exactly five neighbors and two of them (N1 and N2) are using the same color, we know that node X's neighbors have not used all five colors—so you can assign one of the unused colors to node X.

This leads to Rule 2 for simplifying the graph: If the graph contains no nodes with degree less than five, find nodes X, N1, and N2 as described previously and remove all three from the graph. Create a new node N1/N2 to represent the color that nodes N1 and N2 should have and give it the same neighbors that nodes N1 and N2 had. The resulting graph has two fewer nodes than the original. It also has fewer links because you removed the five links to node X, and the new node (N1/N2) has no more links than nodes N1 and N2 did. (It may contain fewer if N1 and N2 had common neighbors.)

Figure 4 shows the graph from Figure 3 after applying Rule 2. In this example, the roles of X, N1, and N2 were played by nodes A, F, and C respectively. I removed nodes A, F, and C, created a new node F/C, and gave it the same links that nodes F and C had. In Figure 4, nodes B and E have degree less than five so Rule 1 applies. Removing those nodes simplifies other nodes so Rule 1 is enough to finish the job.)

 
Figure 5. Applying Coloring Rules: Here's an illustration of the complete algorithm for five-coloring the graph in Figure 3, using both Rules 1 and 2.
After applying Rule 2, you can continue applying the rules to simplify the graph further. Often, (as in this case) applying Rule 2 makes the graph simple enough that you can apply Rule 1 again. Again, you proceed using Rules 1 and 2 until the graph is empty, after which you start adding nodes back into it as before. When you are ready to restore nodes X, N1, and N2, you first remove the artificial node N1/N2. Give N1 and N2 whatever color you assigned to node N1/N2 in the simpler graph. Restore node X and pick a color for it that isn't used by its neighbors. Figure 5 shows the entire process for the graph shown in Figure 3. Follow the arrows to see how the graph is pulled apart with Rules 1 and 2, and then put back together again in the reverse order. As the graph is dismantled, the nodes that will be removed in the following step are highlighted with blue circles. As the graph is rebuilt, the newly added nodes at each step are highlighted similarly.

It is important to note that Rule 1 and Rule 2 both reduce the number of nodes in the graph. That means the graph will eventually run out of nodes, so the process will complete. In other words, the rules prevent an algorithm from simply rearranging the nodes and running forever, reshuffling the nodes but not making any progress. Because both rules remove at least one node from the graph, the process can take at most N steps where N is the number of nodes in the original graph.



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap