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 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, that is to say that 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 S of G is said to be maximal by inclusion if there is no stable 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 maximum stable by inclusion, the converse is not true. The classic heuristic for obtaining a large stable 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 stable vertices in k.
The Welsh and Powell algorithm is based on this proposition:
- Order the vertices of the graph in decreasing 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 next uncolored vertex such that it is not adjacent to the vertex p.
- Return to 2 if there are uncolored vertices in the list. Otherwise return 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. 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 S graph.
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 a 20 degree, and the graph has a total of 810 edges. S is too big to be drawn, but we can get an idea of the structure of S by looking at a partial drawing. The drawing shows the 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 is not a priority order of colors 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.
EN 
FR 
ES