Now, the vertex with maximum degree is ( each group will take a different color. Hence, Vertex (1) and (4) are contracted into one node. Let’s go back to our example. Vertex (1) has the maximum degree its non adjacent vertices are vertex (4). Repeat steps 1-6 until the resulting graph has all contracted nodes adjacent to each other. Remove Y from the set and repeat steps 3-5 until the list is empty.ħ. Contract Y into V to be colored with the same color.ĥ. From this set select the vertex Y of maximum common vertices with V.Ĥ. Find the set of non-adjacent vertices to V.ģ.
A contraction algorithm would work as follows:ġ. The second category “Contraction” works by finding two vertices removing any edges between them, and replacing them with a single vertex where any edges that were connected to any of them are now redirected to new single vertex. Now the graph looks like this and we are left with one vertex which will be colored green. Now the graph looks like this and the new list is 5, 3,2ĭon’t color blue because it is connected to 5
Remove colored vertices from the list and repeat the process until all vertices are colored.ĭon’t color red because it is connected to 1 Go through the list, color each vertex not connected to colored vertices with the same color.Ĥ. Order the vertices in descending order according to their degree.ģ. (Degree: is the number of edges connected to it)Ģ. Algorithms under this category differ in the way the next vertex is selected.Ī famous algorithm under this category is the Welsh–Powell algorithm. Once a vertex is colored, its color never changes. Greedy Coloring focuses on carefully picking the next vertex to be colored. Most of the algorithms can be broadly categorized in one of two main topics “Contraction” and “Greedy Coloring”.
Graph coloring is computationally hard and it has been a research topic for many years. Contraction and Greedy Coloring Algorithms Therefore, the smallest number of colors needed to color a graph is called its chromatic number. If you tried to color the above graph using only two colors you will find out that it cannot be colored at all, Go try it out I will wait :). coloring (1) in the above example is a 3-coloring while coloring (2) is a 5-coloring). A coloring that uses at most k colors is called k-coloring (e.g. Our color is to find a coloring of a given graph that uses the minimum number of colors. Coloring (1) uses the 3 colors while Coloring (2) uses 5 colors, hence, coloring (1) is better than coloring (2). Below are another two possible colorings for the example graph. The goal is to use the minimum number of colors possible. It should be clear by now that one graph can have more than one possible coloring. Below is one possible coloring of this graph. However, vertices 2 and 3 can have the same color because they are not connected. For example, in the graph mentioned above vertices 1 and 2 cannot have the same color because they have an edge connecting them. Graph coloring is the assignment of "colors" to vertices of the graph such that no two adjacent vertices share the same color. The objects are represented by vertices (nodes) and the links are called edges. Graph Coloring DemystifiedĪ graph is a mathematical representation of a set of objects where some pairs of objects are connected (linked) to each other. This article assumes that the reader is already familiar with the concept of a graph and its representation. In this article, I will explain the concept of graph coloring and how it can be used to solve a 9x9 Sudoku Puzzle.
0 kommentar(er)
