You get a bonus - 1 coin for daily activity. Now you have 1 coin

Coloring graphs Algorithm coloring graph. Practical application of graph coloring

Lecture



Coloring graphs

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Correct coloring of graph vertices by the smallest set of colors - three.

In graph theory, the coloring of graphs is a special case of graph marking [en] . When coloring, the elements of the graph correspond to the labels, taking into account certain restrictions; These labels are traditionally called “flowers.” In the simplest case, such a method of coloring the vertices of a graph, in which different colors correspond to any two adjacent vertices, is called vertex coloring . Similarly, edge coloring assigns a color to each edge so that any two adjacent edges have different colors. [1] Finally, the coloring of areas of a planar graph designates the color of each area, so that every two areas that have a common border cannot have the same color.

The coloring of the vertices is the main task of coloring the graphs; all other tasks in this area can be reduced to it. For example, the coloring of the edges of a graph is the coloring of the vertices of its edge graph, and the coloring of the areas of a planar graph is the coloring of the vertices of its dual graph. [1] However, other problems coloring graphs are often posed and solved in the original formulation. The reason for this is partly because it gives a better idea of ​​what is happening and is more revealing, and partly because it is more convenient to solve some problems in this way (for example, coloring of edges).

Coloring graphs is used in many practical areas, not only in theoretical problems. In addition to the classic types of problems, various restrictions may also be imposed on the graph, on the method of assigning colors or on the colors themselves. This method, for example, is used in the popular Sudoku puzzle. Active research is still underway in this area.

Story

The first results were obtained for flat graphs in the problem of coloring maps. Trying to color the map of the districts of England, Francis Guthrie formulated the four colors problem, noting that four colors are enough to color the map so that any two adjacent regions have different colors. His brother referred the question to his math teacher, Augustus de Morgan, who mentioned it in his letter to William Hamilton in 1852. Arthur Cayley raised this issue at a meeting in London in 1878. In the same year, Tate proposed the first solution to this problem. He reduced the coloring of the vertices of the original graph to the edge coloring of the dual graph and suggested that this problem always has a solution. [2] In 1880, Alfred Kempe [en] published an article stating that he was able to establish the result, and the problem of four colors was considered solved for a decade. For this achievement, Kempe was elected a member of the Royal Society of London and later - President of the London Mathematical Society. [3]

In 1890, Hivoud [ru] found a mistake in proving Kempe. In the same article, he proved the five-color theorem, showing that any flat map can be painted in no more than five colors. However, he relied on the ideas of Kempe. In the next century, a large number of theories were developed in an attempt to reduce the minimum number of colors. The four-color theorem was finally proved in 1977 by scientists Kenneth Appel and Wolfgang Hacken using computer brute force. The idea of ​​the proof was largely based on the ideas of Hewood and Kempe and ignored most of the intermediate studies. [4] The proof of the four-color theorem is one of the first proofs in which a computer was used.

In 1912, George David Birkhof proposed to use the chromatic polynomial, which is an important part in algebraic graph theory, to study coloring problems. The chromatic polynomial was subsequently compiled by William Tat (Tatta polynomial). Kempe in 1879 already paid attention to the general case when the graph was not flat. [5] Many results of generalizations of coloring of flat graphs on surfaces of higher orders appeared at the beginning of the 20th century.

In 1960, Claude Berge [ru] formulated a hypothesis about perfect graphs, motivated by the notion of information theorems, namely the zero error of the capacity of the graph [6] , presented by Shannon. The statement remained unconfirmed for 40 years, until it was proved as the famous rigorous theorem on perfect graphs [en] by mathematicians Chudnovskaya [en] , Robertson [en] , Seymour [en] and Thomas [en] in 2002.

The coloring of graphs as an algorithmic problem began to be studied since the 1970s: the definition of the chromatic number is among the 21 NP-complete Karp problems (1972). And at about the same time, various algorithms were developed based on a search with a return and recursive deletion and Zykov contraction. [7] Since 1981, the coloring of the graph has been used to allocate registers in compilers. [eight]

Definition and terminology

Vertex coloring

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

This graph can be colored in 3 colors in 12 ways.

When they talk about coloring graphs, they almost always mean by this the coloring of their vertices, that is, the assignment of color labels to the vertices of the graph so that any two vertices that have a common edge have different colors. Since the graphs in which there are loops can not be colored in this way, they are not the subject of discussion.

The terminology in which labels are called colors comes from the coloring of political maps. Labels such as red or blue are used only when the number of colors is small, but usually it is assumed that the labels are integers {\ \ {1,2,3, ... \}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .

Coloring with {\ k} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring colors called {\ k} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring painting . The smallest number of colors needed to color the graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , is called its chromatic number and is often written as {\ \ chi (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . Sometimes used {\ \ gamma (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring since {\ \ chi (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring denotes the Euler characteristic. A subset of the vertices in one color is called a color class , each such class forms an independent set. Thus, {\ k} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring -coloring is the same as dividing vertices into {\ k} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring independent sets. [one]

Chromatic polynomial

Chromatic polynomial is a function {\ P (G, t)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring which counts the number of t- colorings of the graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . The name implies that for given {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring this function is a polynomial dependent on t . This fact was discovered by Birkhoff and Lewis while trying to prove the hypothesis of four colors. [9]

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

All non-isomorphic graphs from 3 vertices and their chromatic polynomials. The empty graph E 3 (red) allows coloring in one color, the others are not. A green graph can be colored in 3 colors in 12 ways.

For example, the graph in the image on the right can be colored in 12 ways using 3 colors. Two colors it can not be painted in principle. Using 4 colors, we get 24 + 4 * 12 = 72 coloring options: when using all 4 colors, there are 4! = 24 correct ways ( each assignment of 4 colors for any graph of 4 vertices is correct); and for every 3 colors of these 4 there are 12 coloring methods. Then, for the graph in the example, the table of numbers of correct colorings will start like this:

Available number of colors one 2 3 four ...
The number of ways to paint 0 0 12 72 ...

For the graph in the example, {\ P (G, t) = t (t-1) ^ {2} (t-2)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and of course, {\ P (G, 4) = 72} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .

The chromatic polynomial contains at least as much colorization information {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring how much and chromatic number. In fact, {\ \ chi} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - the smallest positive integer that is not the root of the chromatic polynomial.

{\ \ chi (G) = \ min \ {t \, \ colon \, P (G, t)> 0 \}.} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Chromatic polynomials for some graphs
Triangular {\ K_ {3}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring {\ t (t-1) (t-2)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring
Complete graph {\ K_ {n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring {\ t (t-1) (t-2) \ cdots (t- (n-1))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring
Tree with {\ n} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ribs {\ t (t-1) ^ {n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring
Cycle {\ C_ {n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring {\ (t-1) ^ {n} + (- 1) ^ {n} (t-1)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring
Count Petersen {\ t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t-352)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Edge Coloring

The edge coloring of a graph implies the assignment of colors to edges so that no two edges of the same color belong to the same vertex. This task is equivalent to dividing the set of faces into sets of independent faces. The smallest number of colors required for the line coloring of the graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - this is its chromatic index , or an edge chromatic number , {\ \ chi '(G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .

Total coloring

Total coloring is one of the types of coloring of the vertices and edges of the graph. Under it implies such an assignment of colors that neither adjacent vertices, nor adjacent edges, nor vertices and edges that connect them, do not have the same color. Full chromatic number {\ \ chi '' (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - This is the smallest number of colors needed for any full coloring.

Properties

Properties of chromatic polynomial

  • If {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - empty graph [10] ,

{\ P (G, t) = 1} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • If the graph is {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - union of non-intersecting subgraphs {\ H} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and {\ K} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring [10] ,

{\ P (G, t) = P (H, t) P (K, t)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • If in {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring there is a loop [10] ,

{\ P (G, t) = 0} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Chromatic number limits

  • Assigning to all vertices of different colors always gives the correct coloring, so

{\ 1 \ leq \ chi (G) \ leq n. \,} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • The only kind of graphs that can be colored in one color is zero graphs.
  • Complete graph {\ K_ {n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring consisting of {\ n} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring vertices require {\ \ chi (K_ {n}) = n} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring colors.
  • With optimal coloring, there must be at least one edge of {\ m} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring the edges of the graph are between every two color classes, so that [11]

{\ \ chi (G) (\ chi (G) -1) \ leq 2m. \,} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • If {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring is a union of disjoint subgraphs {\ H} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and {\ K} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring then

{\ \ chi (G) = max \ {\ chi (H), \ chi (K) \}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • If {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring contains clicks of size k , then a minimum of k colors is needed to color this click, in other words, the chromatic number is greater, or an equal number number:

{\ \ chi (G) \ geq \ omega (G). \,} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

For interval graphs, this restriction is exact.

  • By the four color theorem, any flat graph can be colored with four colors.
  • 2-colored graphs are bipartite graphs, including trees.

{{ G} graph Coloring graphs Algorithm coloring graph.  Practical application of graph coloring is bipartite if and only if it does not contain cycles of odd length. [ten]

  • The greedy coloring shows that any graph can be colored by using one color more than its maximum vertex degree [11] ,

{\ \ chi (G) \ leq \ Delta (G) +1. \,} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • Complete graphs have {\ \ chi (G) = n} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and {\ \ Delta (G) = n-1} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , graph-cycles have {\ \ chi (G) = 3} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and {\ \ Delta (G) = 2} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring so that for them this limitation is best; in all other cases, the limitation can be improved: Brooks's theorem [12] states that

{\ \ chi (G) \ leq \ Delta (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring for a connected, simple graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring if {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring is neither a complete graph, nor a cycle graph.

Graphs with a large chromatic number

  • Graphs with large cliques have a large chromatic number, but the opposite is not always true. The Grötch graph is an example of a 4-colorable graph without triangles, and this example can be generalized to the Mychelsky graph.

Mychelsky theorem (Alexander Zykov 1949, Jan Mychelsky, 1955): There are graphs without triangles with arbitrarily large chromatic numbers.

  • From the Brooks theorem, graphs with a large chromatic number should have a high maximum degree of apex. Another local condition, due to which the chromatic number can be large is the presence of a large clique. But the colorability of a graph depends not only on local conditions: a graph with a large grip locally looks like a tree, so all the cycles are long, but its chromatic number is not 2:

Erdös theorem : There are graphs with arbitrarily large girth and chromatic number. [eleven]

Chromatic Index Restrictions

  • Edge coloring {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring Is the coloring of the vertices of its linear graph {\ L (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . I.e

{\ \ chi '(G) = \ chi (L (G)). \,} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

  • Moreover [13] ,

Koenig theorem: {\ \ chi '(G) = \ Delta (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring if {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - dicotyledonous.

  • In general, the relationship is much stronger than the Brooks theorem gives for coloring vertices [13] :

Vizing's Theorem: Graph with the maximum degree of the vertex {\ \ Delta} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring has an edge chromatic number {\ \ Delta} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring or {\ \ Delta +1} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .

Other properties

  • A graph is k- chromatic if and only if it has an acyclic orientation [en] , for which the length of the longest path [en] is equal to k . This was proved in the theorem of Gallai - Hasse - Roy - Vitaver [en] [14] .
  • For flat graphs, the coloring of vertices is equivalent to nowhere non-zero flow.
  • About infinite graphs, much less is known. Below are two results for coloring infinite graphs.
  1. If all finite subgraphs of the infinite graph are {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring k -chromatic, then {\ G} is Coloring graphs Algorithm coloring graph.  Practical application of graph coloringalso k -chromatic (it is proved under the assumption of the axiom of choice). This is the formulation of the de Bruin – Erdёos theorem [en] [15] .
  2. If the graph admits full n- coloring for any {\ n \ geqslant n_ {0}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring, then it admits an infinite full coloring. [sixteen]

Open questions

The chromatic number of the plane in which the two points are adjacent if the unit distance between them is unknown. It can be 4, 5, 6, or 7. Other open questions about the chromatic number of graphs include the Hadwiger hypothesis, stating that any graph with chromatic number k has a complete graph of k vertices, like its minor, Erdрдos – Faber hypothesis –Lovasa [en] , which limits the chromatic number of complete graphs that have exactly one common vertex for each pair of graphs, and the Albertson hypothesis [en] that among the k -chromatic graphs, those that have the least number of intersections are complete.

When Birkov and Lewis introduced the chromatic polynomial in their attempt to solve the four-color theorem, they argued that for flat graphs {\ G}, Coloring graphs Algorithm coloring graph.  Practical application of graph coloringthe {\ P (G, t)} polynomial Coloring graphs Algorithm coloring graph.  Practical application of graph coloringdoes not have zeros in the {\ [4, \ infty)}Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .Although it is known that such a chromatic polynomial does not have zeros in the area {\ [5, \ infty)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring, and that {\ P (G, 4) \ neq 0} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring, their assertion remains unproved. It also remains an open question how to distinguish graphs with the same chromatic polynomial, and how to determine that the polynomial is chromatic.

Algorithms coloring

Polynomial algorithms

Для двудольного графа задача раскраски вычисляется за линейное время с помощью поиска в ширину. В случае совершенных графов, хроматическое число и соответствующая ему раскраска может быть найдена за полиномиальное время при использовании полуопределенного программирования [en] . Точные формулы для нахождения хроматического числа известны для многих классов графов (леса, циклы, колеса, хордальные графы) и так же могут быть вычислены за полиномиальное время.

Точные алгоритмы

Алгоритм полного перебора для случая k-раскраски рассматривает все {\ k^{n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring комбинаций расстановки цветов в графе с n вершинами и проверяет их на корректность. Чтобы вычислить хроматическое число и хроматический полином, данный алгоритм рассматривает каждое k от 1 до n. Такой алгоритм на практике может быть применим только для небольших графов.

Используя динамическое программирование и оценку размера наибольшего независимого множества, в графе возможность k-раскраски может быть разрешена за время {\ O(2,445^{n})} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring [17] . Известны более быстрые алгоритмы для 3- и 4-раскрасок, работающие за время {\ O(1,3289^{n})} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring [18] и {\ O(1,7272^{n})} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring [19] соответственно.

Стягивание

Стягивание вершин — это операция, которая из графа {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring делает граф {\ G/uv} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , отождествляя вершины {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , удаляя соединяющих их рёбра, и заменяя на одну вершину{\ w} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , куда перенаправляются ребра инцидентные вершинам {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . Эта операция играет важную роль в анализе раскраски графов.

Хроматическое число удовлетворяет рекуррентному соотношению:

{\ \chi (G)=min\{\chi (G+uv),\chi (G/uv)\}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ,

где {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring несмежные вершины, {\ G+uv} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring граф с добавленным ребром {\ uv} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .

Хроматический полином удовлетворяет рекуррентному соотношению:

{\ P(G-uv,t)=P(G/uv,t)+P(G,t)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ,

где {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring смежные вершины, {\ G-uv} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring граф с удалением ребра {\ uv} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . {\ P(G-uv,t)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring представляет собой число возможных правильных раскрасок графа, когда вершины {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring могут иметь одинаковые или различные цвета. Если {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring имеют разные цвета, тогда мы можем рассмотреть граф, где {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring смежные. Если {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring имеют одинаковые цвета, мы можем рассмотреть граф, где {\ u} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и {\ v} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring объединены.

Выражения данные выше приводят к рекурсивной процедуре, названной алгоритм удаления и стягивания , сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время {\ ((1+{\sqrt {5}})/2)^{n+m}=O(1,6180^{n+m})} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring для n вершин и m рёбер. [20] На практике, метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.

Жадная раскраска

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Два результата работы жадного алгоритма при выборе разных порядков вершин.

Жадный алгоритм упорядочивает вершины {\ v_{1}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ,…,{\ v_{n}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring и последовательно присваивает вершине {\ v_{i}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring наименьший доступный цвет, не использовавшийся для окраски соседей {\ v_{i}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring среди {\ v_{1}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ,…,{\ v_{i-1}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу {\ \chi (G)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим; например, корона с n вершинами может быть раскрашена 2 цветами, но существует порядок вершин, который приводит к жадной раскраске из {\ n/2} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring цветов.

Для хордального графа и для его особых случаев (например, интервальный граф) алгоритм жадной раскраски может быть использован для нахождения оптимальной раскраски за полиномиальное время, выбирая порядок вершин обратным ксовершенному порядку исключения. Этот алгоритм может применен и к более широкому классу графов (совершенно упорядочиваемые графы [en] ), однако найти такой порядок для таких графов — NP-сложная задача.

If the vertices are ordered according to their degrees, the greedy coloring algorithm uses no more than {\ max_ {i} min \ {d (v_ {i}) + 1, i \}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring colors, which is a maximum of 1 more than {\ \ Delta} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring (here {\ d (v_ {i})} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - degree of vertex {\ v_ {i}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ). This heuristic algorithm is sometimes called the Welsh-Powell algorithm. [21] Another algorithm sets the order dynamically, choosing the next vertex of the one that has the greatest number of adjacent vertices of different colors. Many other graph coloring algorithms are based on greedy coloring and use static or dynamic strategies for choosing the order of vertices.

Parallel and distributed algorithms

In the field of distributed algorithms there is a similar problem. Suppose graph vertices are computers that can communicate with each other if they are connected by an edge. The challenge is for each computer to choose a “color” for itself, so that the neighboring computers choose different colors. This task is closely related to the problem of symmetry breaking. The most developed probabilistic algorithms work faster than deterministic algorithms for graphs with a sufficiently large maximum degree of vertices {\ \ Delta} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . The fastest probabilistic algorithms use the technique of multiple attempts [en] [22] .

In symmetric graphs, deterministic distributed algorithms cannot find the optimal coloring of the vertices. Additional information is needed to avoid symmetry. A standard assumption is made that initially each vertex has a unique identifier, for example, from the set {\ \ {1,2, ..., N \}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . In other words, it is assumed that we are given an n- coloring. The goal is to reduce the number of colors from n to, for example, {\ (\ Delta +1)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . The more colors are used (for example, {\ O (\ Delta)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring instead of {\ (\ delta +1)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ), the less message exchanges will be required [22] .

A simple version of the distributed greedy algorithm for {\ (\ Delta +1)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring coloring requires {\ \ Theta (n)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring communication rounds are at worst - information may have to go from one end of the network to the other.

The simplest interesting case is the n- cycle. Richard Cole and Uzi Vishkin [23] showed that there is a distributed algorithm that reduces the number of colors from n to {\ O (log (n))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring by using only one message exchange between neighbors. Repeating the same procedure, we can get the 3-coloring of the n- cycle for {\ O (log ^ {*} (n))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring communication rounds (provided that unique node identifiers are given).

{{ log ^ {*}} function Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , the iterated logarithm, is an extremely slow growing function, "almost constant." Consequently, the results of Cole and Vishkin raise the question of whether there is a distributed n-cycle 3-coloring algorithm that runs in constant time. Nathan Lineal showed that this is impossible: any deterministic distributed algorithm requires {\ \ Omega (log ^ {*} (n))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring communication rounds to reduce N -coloring to 3-coloring in the n-cycle. [24]

The Cole and Vishkin techniques can also be applied to an arbitrary graph with a limited degree of vertices, in this case the running time is {\ P (\ Delta) + O (log ^ {*} (n))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . [25] This method was generalized for the graph of unit circles by Schneider et al. [26]

The problem of coloring the edges was also studied in a distributed model. Pansonezzi and Rizzi reached {\ (2 \ Delta -1)} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring coloring for {\ O (\ Delta + log ^ {*} (n))} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring in this model. [27] The lower limit for the distributed coloring of the vertices achieved by Linial is also applicable to the problem of distributed edge coloring. [24]

Decentralized algorithms

Decentralized algorithms are those in which internal messaging is not allowed (as opposed to distributed algorithms, where processes exchange data with each other). There are effective decentralized algorithms that successfully cope with the task of coloring graphs. These algorithms work on the assumption that the vertex is able to “feel” that any of its neighboring vertices is painted in the same color as it. In other words, it is possible to determine a local conflict. Such a condition is quite often performed in real applications - for example, when transmitting data over a wireless channel, a transmitting station, as a rule, has the ability to detect what the other station is trying to transmit simultaneously to the same channel. The ability to obtain such information is sufficient to ensure that algorithms based on learning automata [en] with a probability of one correctly solve the problem of coloring the graph [28] [29] .

Computational complexity

Coloring a graph is computationally challenging. To find out whether the graph k allows 7-coloring for a given k is an NP-complete problem, except for the cases k = 1 and k = 2. In particular, the problem of calculating the chromatic number is NP-complex. [30] The 3-coloring problem is NP-complete even for the case of a planar graph of degree 4. [31]

Also, an NP-challenge is the coloring of a 3-colored graph with 4 colors [32] and a k- colored graph {\ k ^ {log (k) / 25}} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring for sufficiently large values ​​of k . [33]

Calculating the chromatic polynomial coefficients # P complex task. It is proved that there is not a single FPRAS algorithm for calculating the chromatic polynomial for any rational number k ≥ 1.5, except k = 2, unless it is satisfied that NP = RP. [34]

Application

Planning

Coloring vertices models many planning problems. [35] In its simplest setting, a given set of works should be distributed over time intervals, each such work takes one segment. They can be performed in any order, but two jobs may conflict in the sense that they cannot be performed simultaneously, since, for example, they share resources. The corresponding graph contains a vertex for each of the jobs and an edge for each conflicting pair. The chromatic number of the constructed graph is the minimum execution time for all jobs without conflicts.

Details of the planning problem determine the structure of the graph. For example, when airplanes are distributed among flights, the resulting conflict graph is an interval graph, so the coloring problem can be solved effectively. The distribution of radio frequencies results in a graph of unit circles of conflicts, and for such a problem there is a 3-approximation algorithm.

Register allocation

A compiler is a computer program that translates one computer language into another. To improve the execution time of the resulting code one of the techniques of compiler optimization, is the distribution of registers in which the most frequently used variables of the compiled program are stored in high-speed registers of the processor. In the ideal case, variables are stored in registers so that they are all in registers during their use.

The standard approach to this problem is to reduce it to the problem of coloring graphs. [8] The compiler builds an interference graph , where vertices correspond to registers, and the face connects two of them, if they are needed at the same time. If this graph is k- chromatic, then the variables can be stored in k- registers.

Digital watermarks

Digital watermarking technology (English digital watermarking ) allows along with data (whether it be media files, executable files, and others) to transmit some hidden message ("watermark", Watermark ). Such a hidden message can be used in copyright protection to identify the owner of the data.

This is important, for example, to determine the source of their distribution in an illegal manner. Or to confirm the rights to the data, for example - software systems on a chip ( system-on-chip ).

The message can be encoded including in the method of register allocation. One of these techniques was suggested by Qu and Potkonjak [36] (therefore, it is sometimes called the QP algorithm).

It is this: let {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - incompatibility graph (interference graph) of the distribution of processor registers, which was mentioned above. Its coloring is used in the program - and, it is used in such a way that it is permissible to change the contents of the graph with a small increase in its chromatic number. It turns out that it is possible to encode a message in a software product using the coloring of the graph {\ G} Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , i.e. register allocation.

You can extract this message by comparing the distribution of registers with the original coloring; [37] There are also ways to ascertain whether a certain message was encoded in the program without using the original one.

Later, different authors developed and refined the ideas of Qu and Potkonjak . [38] [39] [37]

Other uses

The task of coloring graphs has been posed in many other areas of application, including pattern matching.

Solving the Sudoku puzzle can be seen as the completion of the coloring with 9 colors of a given graph of 81 vertices.

Coloring graphs (continued) Algorithm coloring graph.

A variety of tasks arising from production planning, scheduling inspection, storage and transportation of goods, etc., can often be presented as problems of graph theory, closely related to the so-called “coloring task” . The graphs considered in this part are unoriented and do not have loops.

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring Let G = (V, E) be an arbitrary graph and {c i , ..., c t } be some set whose elements will be called colors. The t-coloring of a graph G is a map φ of V {{c i , ..., c t } such that for any two distinct adjacent vertices and and v of the graph G, Φ (u)! = Φ (v).
We note that it is not assumed here that φ maps V to the entire set of colors {c i , ..., c t }. We say that the color of Φ (v) is assigned to the vertex v of GV or the vertex of v has the color of Φ (v). We see that the t-coloring of the graph G attributes to each of its vertices one of the t given colors in such a way that any two different adjacent vertices have a different color.

Tricolor coloring Count Petersen

A graph is called t-colored if it possesses t-coloring. A graph is called t-chromatic if it is t-colorable, but not (t - 1) -colorable; the number t in this case is called the chromatic number of the graph G and denoted by x (G).

notice, that
1) 1-chromatics graphs are zero graphs and only they;
2) 2-chromatic graphs are non-zero bipartite graphs and only they;
3) x (K n ) = n and x (G)> = n if the graph G contains the graph K n for a natural number n as a subgraph.

The problem of finding the chromatic number of an arbitrary graph has been the subject of many studies at the end of the 19th and in the current century. Now on this issue a large number of interesting results are known. In this section, we consider an “approximate” algorithm that allows us to find the value of the chromatic number of an arbitrary graph and the coloring of the vertices corresponding to this value.

"Approximate" graph coloring algorithm

The graph coloring algorithm allows finding the (exact or approximate) value of the chromatic number of an arbitrary graph and the corresponding color of the vertices.

A graph G is called r-chromatic if its vertices can be colored using r colors (colors) so that there are no two adjacent vertices of the same color. The smallest number r such that the graph G is r-chromatic is called the chromatic number of the graph G. The task of finding the chromatic number of a graph is called the coloring problem (or coloring problem) of the graph. Corresponding to this number, the coloring of the vertices splits the set of vertices of the graph into r subsets, each of which contains vertices of the same color. These sets are independent, because within the same set there are no two adjacent vertices.

Consider a sequential method based on the ordering of a set of vertices.

Formal description

  Colourize (G)
 1. Arrange the vertices by non-increasing degree.
 2. Color the first vertex in color 1.
 3. Select a color 1.
 4. Until all the vertices are colored, repeat clauses 4.1.-4.2 .:
    4.1.  Color in the selected color any vertex that is not adjacent 
         on the other, already painted in this color.
    4.2.  Select the next color.

In this simplest of methods, the vertices are initially arranged in the order of non-increasing degrees. The first vertex is colored 1; then the list of vertices is viewed from top to bottom (by non-increasing degrees) and in color 1 every vertex is colored, which is not adjacent to another, already painted in this color. Then we return to the first unpainted vertex in the list, paint it in color 2 and again look at the list of vertices from top to bottom, paint in color 2 any unpainted vertex that is not connected by an edge with another vertex painted in color 2. Similarly, we act with colors 3, 4, etc., until all vertices are colored. The number of colors used will then be an approximate value of the chromatic number of the graph.

The above algorithm can be modified. To do this, after each step, you need to order the unpainted vertices. A simple modification of the heuristic procedure described above consists in reordering the unstained vertices by non-increasing their relative degrees. Relative degrees are understood to be the degrees of the corresponding vertices in the uncolored subgraph of the original graph.

In this modification it was assumed that if two vertices have the same degree, then the order of such vertices is random. Such vertices can also be ordered, but by two-step powers. We define a two-step degree as the sum of the relative degrees of the incident vertices. Similarly, you can proceed further.

Complexity assessment

Disregarding the time spent on sorting the vertices in the order of non-increasing degrees, it is necessary to loop through all the vertices of the graph. For each one, it is necessary to find the minimum color, which in the worst case may take o (V 2 ) for the case with a full graph. This means that the total time will be o (V 3 ) in the worst case.

Example

Algorithm Visualizer:

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Arrangements

  1. The graphs considered below are unoriented and do not have loops. Unless specifically stated otherwise, then the word "graph" means just such a graph.
  2. In order not to obstruct the perception of the text by a reader who already has a certain amount of knowledge in the field of graphs, a separate section is reserved for most definitions.

Basic theorems

Lower bounds for γ ( G )

For a start, you can limit the chromatic number of the graph G from below to the click number of the graph. This is obvious because the coloring of a graph click will require a number of colors equal to the number of vertices of this click.

γ ( G ) ≥ ρ ( G )

Now we introduce a more accurate estimate. We use for this the number of vertices in the maximal independent set of the graph G. α ( G ) = ρ ( G ′), where the graph G ′ is the complement of the graph G.

γ ( G ) ≥ [ n / α ( G )] or γ ( G ) ≥ [ n / ρ ( G ′)],

where [] is the integer part of a number. Consider two more estimates introduced in [2].

γ ( G ) ≥] 2 n 0.5 [−γ ( G ′)
γ ( G ) ≥ n / γ ( G ′),

where] [means the smallest integer that is not less than the argument. There is one more estimate, less accurate than the first, but using only the number of vertices and edges of the graph.

γ ( G ) ≥ n 2 / ( n 2 −2 m )

As a result, we can say that the estimates given are rather inaccurate. For example, in [3] it was shown that it is possible to construct a graph that does not even contain a complete third-order subgraph and will have an arbitrarily large value of the chromatic number. At the same time, these estimates give approximately the same accuracy. Therefore, the choice of them should be made on the basis of already calculated data.

Upper estimates for γ ( G )

The lower estimates of the chromatic number are certainly more interesting than the upper ones, since (if they are close enough to the true value) they can be used in the procedure for calculating γ ( G ), including the search tree. At the same time, the upper estimates of the chromatic number of such applications are not found. Nevertheless, formulas are given in the literature for calculating the upper estimates of the chromatic number. For example, in [1], the following easy-to-calculate estimate was proposed:

γ ( G ) ≤ 1 + max ( d ( x i +1)), x i ∈ X

We also give two estimates linking the chromatic number of the graph and the chromatic number of the complement for this graph.

γ ( G ) ≤ n + 1 − γ ( G ′)
γ ( G ) ≤ [( n +1) 2/4] / γ ( G ′)

The above upper and lower bounds using the chromatic number of the complement of the graph under consideration are the most accurate in the sense that it is possible to construct graphs on which these bounds are achieved. But in most cases they are so inaccurate that they have no practical value.

Four Color Theorem

For a long time, the following theorem was the best estimate for planar graphs.

Theorem (about five colors)

Each planar graph can be so colored using five colors so that any two adjacent vertices will be colored in different colors.

And in 1850, the first mentions of the four color hypothesis appeared, which was an improved estimate for planar graphs. This hypothesis was substantiated by computer in 1976, and later proved analytically and received the status of a theorem.

Theorem (of four colors)

Each planar graph can be colored in such a way, using four colors, that any two adjacent vertices will be colored in different colors.

Optimal coloring theorem

Theorem (on optimal coloring)

If the graph G is r- chromatic, then it can be colored using r (or fewer) colors using the following procedure: first, some maximum independent set S ( G ) is colored in one color, then set S is colored into the next color ( X \ S ( G )) and so on until all vertices are colored.

Evidence. The fact that such a coloring, using only r colors, always exists, can be set as follows. Suppose there exists a coloring in r colors, such that one or more sets painted in the same color are not maximal independent sets in the sense mentioned above.

The advantage of this method is that it takes into account cache sizes, cache lines, code “blocks”, and cache associativity. The method is successfully combined with other optimizations and inline-functions [10] [11] . It should be noted that it can be implemented by the optimizer - but not by the optimizer of the compiler, but by the optimizer of the linker.

Frequency distribution

(Eng. Spectrum management , Eng. frequency allocation )

A good work classifying such problems and systematically setting out their solutions is [12] .

The term “frequency allocation” unites different types of tasks, which often have different goals and models. These tasks include:

  • Layout of distribution models (licensing, regulation) of radio frequencies maximizing the use of the entire radio spectrum.
  • Taking into account the fact that it is necessary to allocate the bands for mobile, terrestrial (English point-to-point ) and satellite communications, radio and television broadcasts.
  • Algorithms that dynamically distribute the frequencies of one particular network between users. The cellular communication is of particular interest here, in the field of which a very large amount of research has been done.

The common thing between tasks is that they all produce an optimal distribution of a limited set of radio spectrum resources among users, the number of which is constantly growing in modern conditions.

Two main areas of optimization here:

  • maximizing channel capacity while maintaining a certain minimum level of interference (interference);
  • minimization of interference to achieve a fixed bandwidth.

In the course of considering suitable models, in [12] , problems arise not much more complicated than T-coloring (English T-coloring ) of a multigraph, list T-coloring (English set T-coloring ).

As an example of work on a real cellular network, the results of which were further applied by the operator in their practical activities - [13] (Conducted by the operator E-Plus ((eng.) En: E-Plus) - the 3rd largest in Germany (2010 )).

Parallelization of numerical methods

To summarize, we will present the problem as follows: objects are certain calculations between which it is necessary to divide the computing resources (processors, computers ...) that can work in parallel with each other. Some calculations can be performed in parallel to each other, some - no. Accordingly, the vertex coloring of the incompatibility graph of the calculations is the desired distribution.

Let us give the following examples of numerical methods that can be parallelized in this way:

Cholesky decomposition for the conjugate gradient method with predestination

See also: en: Conjugate gradient method # The preconditioned conjugate gradient method

[14] This method is one of the best iterative methods for solving systems of linear algebraic equations (SLAE) with large, sparse, symmetric, positively defined matrices.

Gauss – Seidel method as applied to sparse matrices

The same iterative method for solving SLAU.

This, in turn, is good, for example, for calculating power distribution grids: such networks can be represented by graphs whose vertices are consumers and sources of electricity, and the edges are power lines; further, a SLAE is constructed, in the matrix of which the diagonal elements correspond to the nodes of the aforementioned graph, and non-zero non-diagonal elements correspond to edges. [15]

Also, the method can be so-called. smoother (English iterative smoother ) for multigrid finite element problem solving methods. (English multigrid methods of finite element problems ). Optimization of the Gauss – Seidel method used in smoothing using the so-called English sparse tiling for such a case of its use is considered in [16] .

Methods using adaptive refined mesh

(English Adaptive mesh refinement )

[17] They, in turn, are useful in solving partial differential equations (DPEs). The clarification principle here is this: in places where the greatest local error is expected — where the solution changes most rapidly, the grid density is chosen to be greater.

Coordinate relaxation method

(eng. method of coordinate relaxation )

[18] It is successfully used in finding the extremal eigenvalues ​​of very large sparse symmetric matrices. Sometimes so large that it is more practical to generate them on the fly than to store them in memory. Such problems often arise in quantum mechanics.

Predetermining incomplete LU decomposition

( Preconditioning by ILU, Incomplete LU-factorization )

To solve the slau using the Krylov subspaces. [nineteen]

Derivative Calculation

Calculation of matrices of derivatives (Jacobians and Hessians) in the case when they are sparse, can be seriously accelerated by coloring the graphs. There is a project "Graph Coloring for Computer Derivatives", site - [www 3] . The site contains publications on the topic, as well as - a software package, in which the project participants have drawn up their achievements. For an introduction to the subject, you can see one of the presentations related to the project - [20] .

For a simple case when the “compaction” of a derivative is limited to a decrease in the number of columns, we give an algorithm:

Input : function from vector - Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

Output : derivative Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - Jacobian or Hessian

1. Investigate the structure of the sparseness of the derivative Coloring graphs Algorithm coloring graph.  Practical application of graph coloring (we will not calculate the derivative itself).

2. Make a matrix Coloring graphs Algorithm coloring graph.  Practical application of graph coloring reduce the number of columns Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - English seed matrix ; make up so that Coloring graphs Algorithm coloring graph.  Practical application of graph coloring was the smallest.

3. Calculate the compacted values Coloring graphs Algorithm coloring graph.  Practical application of graph coloring ; we will not calculate by this formula, but in a different way. Here it is clear that reduced before Coloring graphs Algorithm coloring graph.  Practical application of graph coloring - number of columns Coloring graphs Algorithm coloring graph.  Practical application of graph coloring

4. And now, restore the values Coloring graphs Algorithm coloring graph.  Practical application of graph coloring by Coloring graphs Algorithm coloring graph.  Practical application of graph coloring (can be some direct methods, it is possible - by solving equations).

Coloring graph here - in the calculation Coloring graphs Algorithm coloring graph.  Practical application of graph coloring . In simple cases, it is necessary to calculate the usual vertex (born distance-1 ); distance-2 coloring (which, including reduced to square -distance distance-1 coloring); in more complex, small additional restrictions are required:

  • star coloring ( star coloring ) - vertex distance-1 , but with an additional restriction: for any path from 4 vertices at least 3 colors are used;
  • acyclic coloring ( acyclic coloring ) - vertex distance-1 + each cycle uses at least 3 colors.

Within the framework of the above project, calculations were carried out for technical production problems:

  • the process of chromatographic separation (from the field of chemistry, chemical technology) by means of English technology. Simulated Moving Bed ;
  • solution of the problem of optimal energy flow ( optimal power flow ) (electric power industry).

Digital watermarks

Digital watermarking technology (English digital watermarking ) allows along with data (whether it be media files, executable files, and others) to transmit some hidden message ("watermark", Watermark ). Such a hidden message can be used in copyright protection to identify the owner of the data.

This is important, for example, to determine the source of their distribution in an illegal manner. Or to confirm the rights to the data, for example - software systems on a chip ( system-on-chip ).

The message can be encoded including in the column. One of these techniques was proposed by Qu and Potkonjak (therefore, it is sometimes called the QP algorithm) in [21] .

It consists of this: let's say we have a graph G, the coloring of which is used in the program - moreover, it is used in such a way that it is permissible to change the contents of the graph with a slight increase in its chromatic number. What is important, one of such examples is the incompatibility graph of the register of the processor, which was mentioned above, which means that we will be able to encode the message in a software product using the distribution of registers.

You can extract it by comparing the resulting graph with the original one; there are also ways to ascertain whether a message was encoded in the graph without using the original one — the extraction is described in more detail, for example, in [22] .

The development and refinement of the thoughts of Qu and Potkonjak , attempts to improve the algorithm occur in [23] , [24] , [22] .

Note that in [23] , [24] there are references to the SandMark software package, in which algorithms of this kind are executed; available for download at [www 4] .

Other applications

  • The classical map coloring problem: tops - countries; edges - common borders. Such a graph corresponding to the map is planar, which means, by the 4-color theorem, always χ ≤ 4.
  • Calculation of networks OKS-7 (some generalization of telephone networks); namely, multigraph coloring with some restrictions is needed when routing packets with regard to uniform load [25] . In general, PFUR, including the author [25] who worked there, took an active part in the calculation of the Russian long-distance network OKS-7 [26] - which means the reliability of the source.
  • Cluster analysis (separation of objects into so-called clusters; within a cluster, objects have similar properties and / or clusters have distinct differences) [27] .
  • Solution sudoku: 9 digits sudoku - 9 colors. The vertices of the incompatibility graph are the cells of the table. Ribs between Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and Coloring graphs Algorithm coloring graph.  Practical application of graph coloring hold if and only if:
    • Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , or,
    • Coloring graphs Algorithm coloring graph.  Practical application of graph coloring , or,
    • Coloring graphs Algorithm coloring graph.  Practical application of graph coloring and Coloring graphs Algorithm coloring graph.  Practical application of graph coloring .
  • Designing devices where the wires connected in one node must have different colors for the convenience of distinguishing.
created: 2014-10-13
updated: 2021-12-09
136019



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms