-
Book Overview & Buying
-
Table Of Contents
C# Data Structures and Algorithms - Second Edition
By :
The topic of finding the MST is not the only graph-related problem. Among others, node coloring exists. It aims to assign colors (numbers) to all nodes to comply with the rule that there cannot be an edge between two nodes with the same color. Of course, the number of colors should be as low as possible. Such a problem has some real-world applications, such as for coloring a map. The implementation of the coloring algorithm, which is shown in this chapter, is quite simple and in some cases could use more colors than is necessary.
Four-color theorem
Did you know that the nodes of each planar graph can be colored with no more than four colors? If you are interested in this topic, take a look at the four-color theorem (http://mathworld.wolfram.com/Four-ColorTheorem.html). Since I am talking about a planar graph, you should understand that it is a graph whose edges do not cross each other while it is drawn on the plane.
Let’s take a look at the following diagram...