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.
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.
The following graph has a clique of order 5:
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)
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.
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:
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.