Graph coloring
The graph coloring problem, for a graph G undirected, consists in assigning a color to each vertex in such a way that the same color is not assigned to two adjacent vertices.
When the graph is planar, this amounts to the problem of coloring a geographical map. The problem of graph coloring arises in many practical areas such as pattern matching, planning sports, designing seating plans, reviewing timetables, scheduling taxis, and solving Sudoku.
The minimum number of colors necessary to color the graph G is called the chromatic number of G, and is denoted by X (G).
The problem of finding the chromatic number of a graph is an Np-complete problem. The problem of coloring a graph with a limited number of colors – is it possible to color the graph with x colors, if so how? – is also an Np-complete problem.
A planar graph is at most 4-chromatic.
A chain is at most 2-chromatic.
A cycle is at most 3-chromatic.
A clique of size n is n-chromatic.
Example: A given set of tasks must be assigned to time intervals, each task requires only one interval. Tasks can be scheduled in any order, but task pairs can conflict in the sense that they cannot be assigned to the same time interval, for example because they both rely on a shared resource . The corresponding graph contains a vertex for each job and an edge for each pair of conflicting jobs. The chromatic number of the graphic is exactly the minimum required, the optimal time to complete all work without conflicts.
Problem: clicks
Given an undirected graph G, a clique is a subset of vertices which are all connected in pairs by edges. In other words, it is a complete subgraph.
Find a click w of order k in a graph is an Np-complete problem.
The following graph has a clique of order 5:
Problem: stable
Given an undirected graph G, a stable is a subset of vertices which are not connected in pairs by edges. Finding a stable of order k amounts to finding a clique of order k in the inverse graph, ie it has an edge if it does not exist in the original graph, and vice versa.
Find a stable To of order k in a graph is an Np-complete problem.
Relationship between the three problems and heuristics
We have the following three proposals:
- a (G) = w (not G)
- w (G) = a (not G)
- X (G)> = w (G)
A stable set S of G is said to be maximal by inclusion if there does not exist a stable set S' of G such that S is strictly contained in S'. A clique K is maximal by inclusion if there are no cliques K' of G such that K is strictly contained in K'.
By this definition, we deduce that a stable of maximum order is also a maximal stable by inclusion, the converse is not true. The classical heuristic to obtain a stable of large size is to seek a maximal stable by inclusion.
The Brélaz algorithm is a algorithm greedy which allows to know a maximum limit of the chromatic number of a graph. Its principle is simple and iteratively proceeds.
As long as there is an uncolored vertex, we choose the uncolored vertex with the highest number of neighbors colored with different colors. This vertex is then colored with the smallest possible color (the colors are sorted in an arbitrary ascending order). If all the existing colors are already used by a neighbor, we add a new color to our palette (adding a color with a higher value than all the other existing ones).
The notion of stable can also provide indications on the coloring of a graph. Indeed, we can assume that in a stable, all the vertices have the same color. Coloring in k colors amounts to finding a partition of the set of vertices into stable k.
Welsh and Powell's algorithm is based on this proposition:
- Rank the vertices of the graph in descending order of their degree
- Going through the list in order, assign an unused color to the first uncolored vertex p, and assign this color to each subsequent uncolored vertex such that it is not adjacent to the vertex p.
- Roll back to 2 if there are uncolored vertices left in the list. Otherwise resend the list.
Example
To see the connection between Sudoku and graph coloring, we will first describe the Sudoku graph, which we will call for convenience S. The graph S has 81 vertices, each vertex representing a cell. When two cells cannot have the same number (either because they are in the same row, in the same column, or in the same box), we put an edge connecting the corresponding vertices of the Sudoku graph S.
For example, since cells a3 and a7 are in the same row, there is an edge joining their corresponding vertices; there is also an edge connecting a1 and b3 (they are in the same box), and so on. Each vertex in the Sudoku graph has 20 degree, and the graph has a total of 810 edges. S is too large to be to draw, but we can get an idea of the structure of S by looking at a partial drawing. The drawing shows all 81 vertices of S, but only two (a1 and e5) have their full set of incident edges.
The second step in converting a Sudoku puzzle into a graph coloring problem is to assign colors to the numbers 1 through 9. This assignment is arbitrary and not a color priority order as in the algorithm gluttonous.
Once we have the Sudoku graph and an assignment of colors to the numbers 1 to 9, any Sudoku puzzle can be described by a Sudoku graph where some of the vertices are already colored (those corresponding to the data). To solve the Sudoku puzzle, all we have to do is color the rest of the vertices using the nine colors.
